https://www.acmicpc.net/problem/1309 풀이: a[i] 가 2 x i 칸에 채울 수 있는 배치의 최댓값이라 하자. a[i] = 2 * a[i - 1] + a[i - 2] 로 구할 수 있다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 #include <iostream>using namespace std; int main(void) { int n; cin >> n; int a[100001] = { 3,7,0 }; for (int i = 2; i < n; i++) { a[i] = (2* a[i - 1] + a[i - 2]) % 9901; } cout << a[n - 1] % 9901 << endl; return 0; }

https://www.acmicpc.net/problem/1520 풀이: cnt[i][t] 가 i행 t열을 골랐을 때 최대 경로의 수 이다. 왼쪽 위 부터 차례대로 방문한다. 왼쪽, 오른쪽, 위, 아래 를 모두 검사하여 지금 계단의 지점보다 낮은 지점을 찾는다. 계속 검사하면서 가다가 오른쪽 끝 즉, (n,m) 을 만나면 return 1을 해준다. 시간초과 때문에 재방문을 피하기위해 cnt의 값을 모두 -1로 바꿔놓고 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 28 29 30 31 #include <iostream>using namespace std; int n, m; int a[501][501]; int cnt[501][501]; int downhill(int q, int w) { if (q == n && w == m) return 1; if (cnt[q][w] >= 0) return cnt[q][w]; cnt[q][w] = 0; int x[5] = { 0, 1, 0, -1, 0 }; int y[5] = { 0, 0, 1, 0, -1 }; for (int i = 0; i < 5; i++) { if (q + x[i] > 0 && q + x[i] <= n && w + y[i] > 0 && w + y[i] <= m && a[q + x[i]][w + y[i]] < a[q][w]) { cnt[q][w] += downhill(q + x[i], w + y[i]); } } return cnt[q][w]; } int main(void) { cin >> n >> m; for (int i = 1; i <= n; i++) { for (int t = 1; t <= m; t++) { cin >> a[i][t]; } } fill(cnt[0],cnt[500], -1); cout << downhill(1,1) << endl; return 0; }

https://www.acmicpc.net/problem/1965 풀이: b[i] 가 i 번째 상자를 골랐을 때의 상자의 최대 갯수라고 하자. b[i] = b[i] + 0~i 번째 까지 중 가장 큰 값 이다. 코드: 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 <algorithm>using namespace std; int main(void) { int n,temp; cin >> n; int a[1001] = { 0 }; int b[1001]; 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/2133 풀이: N이 홀수라면 타일을 채울 수 없으므로 언제나 0을 출력한다. 짝수일경우 i를 N/2-1 로 생각하고 a[i] = 4 * a[i - 1] - a[i - 2] 로 구한다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream>#include <math.h>using namespace std; int main(void) { int n; long long a[30] = { 3,11,0 }; cin >> n; if (n % 2 == 1) cout << "0" << endl; else { for (int t = 2; t < n/2; t++) { a[t] = 4*a[t-1] - a[t-2]; } cout << a[n/2-1] << endl; } return 0; }

https://www.acmicpc.net/problem/6359 풀이: n 개의 방이 있을 때 탈출할 수 있는 사람의 수는 sqrt(n)명이다. 코드: 1 2 3 4 5 6 7 8 9 10 11 12 #include <iostream>#include <math.h>using namespace std; int main(void) { int n,T; cin >> T; for (int i = 0; i < T; i++) { cin >> n; cout << (int)sqrt(n) << endl; } return 0; }

https://www.acmicpc.net/problem/10844 풀이: a[i][t] 는 길이가 i인 숫자에서 1의 자릿 수가 t일 때의 경우의 수 t가 0 이면 a[i][t] = a[i - 1][t + 1] t가 9 이면 a[i][t] = a[i - 1][t - 1] 둘다 아니면 a[i][t] = (a[i - 1][t - 1] + a[i - 1][t + 1]) 이 때 오버플로우가 발생하므로 각각의 계산에 1000000000을 나눠준다. 코드: 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>using namespace std; long long a[101][10] = { 0 }; int main(void) { int n; cin >> n; long long cnt = 0; for (int i = 1; i < 10; i++) { a[0][i] = 1; } for (int i = 1; i < n; i++) { for (int t = 0; t < 10; t++) { if (t == 0) a[i][t] = a[i - 1][t + 1] % 1000000000; else if (t == 9) a[i][t] = a[i - 1][t - 1] % 1000000000; else a[i][t] = (a[i - 1][t - 1] + a[i - 1][t + 1]) % 1000000000; } } for (int i = 0; i < 10; i++) { cnt += a[n - 1][i] % 1000000000; } cout << cnt % 1000000000 << endl; return 0; }