https://www.acmicpc.net/problem/11057 풀이: a[i][t] 는 길이가 i인 수에서 1의 자리가 t인 수의 오르막 수의 개수 a[i][t] += max(a[i - 1][t], a[i][t - 1]); 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream>#include <algorithm>using namespace std; int a[1002][1002] = { 0 }; int main(void) { int n, m; cin >> n >> m; for (int i = 1; i <= n; i++) { for (int t = 1; t <= m; t++) { cin >> a[i][t]; } } for (int i = 1; i <= n; i++) { for (int t = 1; t <= m; t++) { a[i][t] += max(a[i - 1][t], a[i][t - 1]); } } cout << a[n][m] << endl; return 0; }

https://www.acmicpc.net/problem/11727 풀이: a[i] 는 타일이 2xi 일때의 경우의 수 a[i] = (2 * a[i - 2] + a[i - 1] 주어진 조건에서 10007으로 나눈 나머지를 출력하라고 하였으므로 나눠줌. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 #include <iostream>using namespace std; int a[1001] = { 1,3,0 }; int main(void) { int n; cin >> n; for (int i = 2; i < n; i++) { a[i] = (2 * a[i - 2] + a[i - 1])%10007; } cout << a[n - 1] << endl; return 0; }

https://www.acmicpc.net/problem/1699 풀이: q[i] 는 i 일 때 제곱수로 나타낼 수 있는 최소의 경우의 수 n 이 i + t^2 으로 나타내 질 때, 최소의 경우의 수를 찾음 코드: 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>#include <math.h>int q[100002] = { 0 }; using namespace std; int main(void) { int n,a; cin >> n; a = sqrt(n); for (int i = 1; i <= n; i++) { q[i] = 10001; for (int t = 1; t <= a; t++) { if (i == t*t) q[i] = 1; } } for (int i = 1; i <= n; i++) { for (int t = 1; t <= a; t++) { if (i + (t*t) <= n && q[i + (t*t)] > q[i] + 1) q[i + (t*t)] = q[i] + 1; } } cout << q[n] << endl; }

https://www.acmicpc.net/problem/1912 풀이: a[i] 는 i번째를 골랐을 때, 최대값 만약 a[i-1] 이 0 보다 크다면, a[i] += a[i-1] 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream>#include <algorithm>using namespace std; int a[100001] = { 0 }; int main(void) { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int temp = a[0]; for (int i = 1; i < n; i++) { if(a[i-1] > 0) a[i] += a[i - 1]; temp = max(temp, a[i]); } cout << temp << endl; return 0; }

https://www.acmicpc.net/problem/2163 풀이: N x M 크기의 초콜릿을 자르는 최소의 경우의 수 N * M - 1 코드: 1 2 3 4 5 6 7 8 #include <iostream>using namespace std; int main(void) { int n, m; cin >> n >> m; cout << n*m - 1 << endl; return 0; }

https://www.acmicpc.net/problem/9461 풀이: a[i] 는 i 번째 수열 a[i] = a[i-1] + a[i-5] 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include <iostream>using namespace std; long long a[101] = { 1,1,1,2,2,0 }; int main(void) { int T,n; cin >> T; for (int i = 0; i < T; i++) { cin >> n; for (int t = 5; t < n; t++) { a[t] = a[t - 1] + a[t - 5]; } cout << a[n - 1] << endl; } return 0; }