https://www.acmicpc.net/problem/11055 풀이: 배열의 이전을 돌며 가장 합이 큰 값을 더함 코드: 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 #include <iostream>#include <algorithm>using namespace std; int a[1002], maxA[1002]; int main(void) { int n; cin >> n; int maximum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; maxA[i] = a[i]; } for (int i = 0; i < n; i++) { int temp = 0; for (int t = i-1; t >= 0; t--) { if (a[t] < a[i]) { temp = max(temp, maxA[t]); } } maxA[i] += temp; maximum = max(maximum, maxA[i]); } cout << maximum << endl; return 0; }

https://www.acmicpc.net/problem/2957 풀이: 트리의 루트에서 부터 왼쪽 오른쪽에 삽입할때 마다 높이를 1씩 증가시켜 준다. cin , cout을 사용할 경우 시간초과가 나므로 scanf, printf 를 사용하도록 하자 출력의 사이즈가 int 사이즈를 넘어가므로 long long 을 사용하자 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream>#include <map>#include <algorithm>#include <stdio.h>using namespace std; int main(void) { int n, num; cin >> n; map<int, long long int> a; a[300001] = -1; a[0] = -1; long long temp = 0; for (int i = 0; i < n; i++) { scanf_s("%d", &num); a[num] = max((--a.

https://www.acmicpc.net/problem/2225 풀이: a[i][t] 는 0~i+1 까지 정수 t+1 개를 더하여 그 합이 i+1 이 되는 경우의 수 이다. a[i][t] = a[i-1][t] + a[i][t-1] 로 나타낼 수 있다. 이때 수의 값이 너무 커져 오버플로우가 발생할 수 있으므로 1000000000으로 나눈 나머지를 출력한다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream>using namespace std; long long a[201][201]; int main(void) { int n, k; cin >> n >> k; for (int i = 0; i < n; i++) { a[i][0] = 1; for (int t = 1; t < k; t++) { if (i == 0) a[i][t] = t + 1; else a[i][t] = ((a[i - 1][t]) % 1000000000 + (a[i][t - 1]) % 1000000000) % 1000000000; } } cout << a[n - 1][k - 1] << endl; return 0; }

https://www.acmicpc.net/problem/11051 풀이: nCk 를 나타내는 함수 Comb() 를 만든다. 재귀함수의 특성상 시간초과 때문에 배열에 값을 저장해놓는다. 참고: 1010 다리놓기 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream>using namespace std; long long cnt[1001][1001] = { 0 }; int Comb(int n, int r) { if (r == 0 || r == n) return 1; else if (r == n - 1 || r == 1) return n; if (cnt[n - 1][r] == 0) cnt[n - 1][r] = Comb(n - 1, r); if (cnt[n - 1][r - 1] == 0) cnt[n - 1][r - 1] = Comb(n - 1, r - 1); return (cnt[n - 1][r] % 10007 + cnt[n - 1][r - 1] % 10007) % 100007; } int main(void) { int n, k; cin >> n >> k; cout << Comb(n, k) % 10007<< endl; return 0; }

https://www.acmicpc.net/problem/1890 풀이: cnt[[x][y] 는 x열 y행 에서의 최대 경로의 개수 시간초과를 막기위해 if (cnt[x][y] >= 0) 를 넣어 중복을 피함 코드: 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 #include <iostream>using namespace std; int n, a[101][101]; long long cnt[101][101]; long long jump(int x, int y) { if (x == n - 1 && y == n - 1) return 1; if (cnt[x][y] >= 0) return cnt[x][y]; cnt[x][y] = 0; if (a[x][y] + x < n) cnt[x][y] += jump(a[x][y] + x, y); if (a[x][y] + y < n) cnt[x][y] += jump(x, a[x][y] + y); return cnt[x][y]; } int main(void) { cin >> n; for (int i = 0; i < n; i++) { for (int t = 0; t < n; t++) { cin >> a[i][t]; } } fill(cnt[0], cnt[100], -1); cout << jump(0, 0) << endl; return 0; }

https://www.acmicpc.net/problem/2096 풀이: b[i][0] 은 i번째 수를 골랐을 때의 최댓값 b[i][0] 은 i번째 수를 골랐을 때의 최솟값 참고: 1149 RGB거리 코드: 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 <algorithm>using namespace std; int a[3],c[3]; int main(void) { int n,temp; cin >> n; int b[2][3] = { 0 }; for (int i = 0; i < n; i++) { cin >> a[0] >> a[1] >> a[2]; c[0] = b[0][0]; c[1] = b[0][1]; c[2] = b[0][2]; temp = max(c[1], c[0]); b[0][0] = a[0] + temp; b[0][1] = a[1] + max(temp, c[2]); b[0][2] = a[2] + max(c[1], c[2]); c[0] = b[1][0]; c[1] = b[1][1]; c[2] = b[1][2]; temp = min(c[1], c[0]); b[1][0] = a[0] + temp; b[1][1] = a[1] + min(temp, c[2]); b[1][2] = a[2] + min(c[1], c[2]); } temp = max(b[0][1], b[0][0]); cout << max(temp, b[0][2]) << " "; temp = min(b[1][1], b[1][0]); cout << min(temp, b[1][2]) << endl; return 0; }