https://www.acmicpc.net/problem/3908 풀이: 소수를 찾는다. 소수를 하나씩 추가해가면서 a[n][k]를 찾는다. a[n][k] : 양의 정수 n을 서로 다른 k개의 소수의 합으로 나타낼 수 있는 최대의 경우의 수 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include <iostream>#include <vector>#include <math.h>#include <string.h>using namespace std; int T, n, k, a[1122][16] = { 0 }; bool isprime[1122]; vector<int> b; int prime() { memset(isprime, 1, sizeof(isprime)); isprime[0] = isprime[1] = false; for (int i = 2; i < sqrt(1122); i++) if(isprime[i]) for (int t = i * i; t < 1122; t += i) isprime[t] = false; for (int i = 2; i < 1122; i++) if (isprime[i]) b.

https://www.acmicpc.net/problem/2748 풀이: a[i % 3] : n번째 피보나치 수 a[i % 3] = a[(i - 1) % 3] + a[(i - 2) % 3]; 코드: 1 2 3 4 5 6 7 8 9 #include <iostream>using namespace std; long long a[3] = { 0,1 }, n; int main() { cin >> n; for (int i = 2; i <= n; i++) a[i % 3] = a[(i - 1) % 3] + a[(i - 2) % 3]; cout << a[n % 3] << endl; }

https://www.acmicpc.net/problem/11568 풀이: 11053 가장 긴 증가하는 부분 수열 의 문제와 같으므로 링크를 참고 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <iostream>#include <algorithm>using namespace std; long long a[1001] = { 0 }, b[1001]; int main(void) { long long n, temp; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; b[i] = 1; } for (int i = 0; i < n; i++) { temp = 0; for (int t = 0; t <= i; t++) { if (a[i] > a[i - t]) temp = max(b[i - t], temp); } b[i] += temp; } for (int i = 0; i < n; i++) { temp = max(b[i], temp); } cout << temp << endl; return 0; }

https://www.acmicpc.net/problem/2228 풀이: dp[n][m] : n개의 숫자를 m개의 구간으로 나눈 최대 합 dp[i][t] = dp[i - 1][t] : i번째 수를 포함하지 않는 경우 dp[i][t] = max(dp[i][t], (t == 1 ? 0 : dp[y - 1][t - 1]) + a[i] - a[y]) : i번째 수를 포함하는 경우 i번째를 포함하므로 구간을 하나 빼고 그것에 i번째 수를 포함하는 구간을 더한다. max함수를 쓰므로 dp 초기화를 잘해줘야한다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream>#include <algorithm>using namespace std; int a[101] = { 0 }, dp[101][52] = { 0 }; int main(void) { int n, m, temp; cin >> n >> m; fill(dp[0] + 1, dp[0] + m + 1, -2147483646); for (int i = 1; i <= n; i++) { cin >> temp; a[i] = a[i - 1] + temp; for (int t = 1; t <= m; t++) { dp[i][t] = dp[i - 1][t]; for (int y = i - 1; y / 2 >= t - 1; y--) { dp[i][t] = max(dp[i][t], (t == 1 ?

https://www.acmicpc.net/problem/7579 풀이: 처음 문제를 풀때는 DP[메모리]로 풀었더니 시간초과가 났다. 그래서 DP[c]로 풀게되었다. 가격이 0이고 메모리가 0인 지점부터 하나하나 더해가면서 만들어나간다. 그 후 가격이 낮은 곳부터 검사하면서 메모리가 M값보다 높아지면 출력한다. iter = a.end(); 를 처음에 iter = a.begin(); 으로 했을 때 출력이 잘못되는 것을 발견하였다. 아마 작은 값부터 더해가는 과정에 겹치는 값이 생겼을 것이라고 본다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include <iostream>#include <map>#include <algorithm>using namespace std; map<int, int> a; int k[101], c[101]; int main(void) { int n, m, size, temp; cin >> n >> m; a[0] = 0; for (int i = 0; i < n; i++) cin >> k[i]; for (int i = 0; i < n; i++) cin >> c[i]; map<int, int>::iterator iter; for (int i = 0; i < n; i++) { size = a.

https://www.acmicpc.net/problem/1038 풀이: 10, 321 등 감소하는 수를 찾는 문제 감소하는 수를 하나씩 만들어 가면서 카운트를 증가시킨다. 카운트의 값이 제시된 N값과 일치하면 출력한다. 제시된 N값이 9876543210의 위치인 1022 보다 크다면 -1을 출력한다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 #include <iostream>#include <vector>using namespace std; vector<int> a; int main(void) { int n; int cnt = 11; cin >> n; if (n < 11) { cout << n << endl; } else if (n > 1022) cout << "-1" << endl; else { a.