목록수학 (34)

1일1알

백준 1699번 제곱수의 합 C++

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net dp[n]의 최솟값은 dp[n - a^2] + 1 중 최솟값이다. (a^2 > n; vector dp(n + 1); for (int i = 1; i
알고리즘 2022. 10. 8. 12:02
백준 1644번 소수의 연속합 C++

에라토스테네스의 체를 이용해서 소수만 들어가있는 배열을 만들고 그 배열에서 투 포인터를 이용해서 누적합이 n보다 작으면 오른쪽 포인터를 증가시키고 반대면 왼쪽 포인터를 증가시키면서 누적합이 n과 같은 경우의 수들을 찾았다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; vector isPrime; vector primes; int main() { ios_base::sync_with_stdio(false)..
알고리즘 2022. 7. 19. 10:48
백준 10830번 행렬 제곱 C++

a^b에서 b가 홀수라면 b를 1 빼주고 결과(처음에는 단위행렬)에 a를 곱해주고 b가 짝수라면 a^b = (a^2)^(b/2) 이기 때문에 a를 제곱해주고 b를 2로 나눠주었다. 2^7를 예로 들자면 우선 처음에 결과는 1로 시작한다. (res = 1) 2^7 에서 7이 홀수이기 때문에 2^6 으로 바꾸고 res에 2를 곱한다 (res = 2) 2^6 에서 6이 짝수이기 때문에 4^3으로 바꿔준다. 4^3에서 3이 홀수이기 때문에 4^2로 바꿔주고 res에 4를 곱한다(res = 8) 4^2에서 2가 짝수이기 때문에 16^1로 바꿔준다. 16^1에서 1이 홀수이기 때문에 16^0으로 바꿔주고 res에 16을 곱한다(res = 128) b가 0이 됐기 때문에 그만 계산한다. 2^7 = res = 128이..
알고리즘 2022. 6. 29. 11:08
백준 1629번 곱셈 C++

분할 정복을 이용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int64 solve(int64 a, int64 b, int64 c) { if (b == 1) return a % c; int64 tmp = solve(a, b / 2, c); if (b % 2 == 0) return tmp * tmp % c; return ((tmp * tmp) % c * a) % c; } int main() { ios_base..
알고리즘 2022. 6. 11. 13:28
백준 2407번 조합 C++

파이썬으로 하면 그냥 계산하면 되지만 C++에서는 int64 범위를 넘어가기 때문에 문자열로 처리해야 한다. 조합 계산은 파스칼의 삼각형을 이용해 메모이제이션과 재귀 방식을 이용하였고 수를 더할때는 문자열을 이용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; vector cache; string Combination(int n, int m) { if (m == 0 || m == n) return "1"; strin..
알고리즘 2022. 6. 10. 11:21
백준 2417번 정수 제곱근 C++

sqrt를 사용하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll n; cin >> n; ll q = sqrt(n); if (q * q >= n) cout
알고리즘 2022. 5. 11. 13:09
이전 Prev 1 2 3 4 5 6 Next 다음