https://www.acmicpc.net/problem/2352 풀이: 맨 처음 값부터 하나 하나 입력받는다. 입력받은 값이 벡터 안에 있는 값들 보다 크다면 벡터에 맨 뒤에 넣는다. 벡터의 처음부터 검색했을 때, 입력받은 값보다 큰 값이 있다면, 그 값과 교체한다. 벡터의 원소 갯수를 출력한다. 일반적으로 for문을 두개 쓴 O(n^2)의 코드는 시간초과가 나므로 주의하자 코드: 사용언어 : c++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <iostream>#include <algorithm>#include <vector>using namespace std; vector<int>d; int main(void) { int n, s, l; cin >> n; while(n--) { cin >> s; l = lower_bound(d.

https://www.acmicpc.net/problem/1495 풀이: dp[a][b]를 a 번째 곡을 연주 할 때, b 볼륨으로 연주 할 수 있는가? 라고 하자. dp[0][S]는 0 번째 곡을 연주 할 때, S 볼륨으로 연주할 수 있으므로(시작지점) 1을 할당한다. 0번째 곡을 연주할 때, S볼륨으로 연주가 가능하다면, 1번째 곡을 연주할 때, S+s[1] or S-s[1] 볼륨도 연주 가능하다(0<=볼륨<=m 일때) 즉, dp[i][t + s[i]] = dp[i - 1][t] or dp[i][t - s[i]] = dp[i - 1][t] 마지막에 dp[N]값을 모두 순환하며, 가장 높은 값을 출력하고, 가능한 볼륨이 없다면 -1을 출력한다.

https://www.acmicpc.net/problem/4781 풀이: dp[a]를 a원으로 구매할 수 있는 가장 높은 칼로리라고 한다. 사탕의 칼로리를 s, 가격을 d라고 했을 때, 현제 a원으로 구매할 수 있는 가장 높은 칼로리와 a-d원 으로 구매할 수 있는 가장높을칼로리 + s 를 비교하여 높은 값으로 교체한다. 즉, dp[t] = max(dp[t], dp[t - d] + s) 를 반복하여 do[m]값을 구한다. 코드: 사용언어 : c++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iostream>#include <cstring>#include <algorithm>using namespace std; double M1, d1; int N, M, s, d, dp[10002]; int main(void) { while (1) { memset(dp, 0, sizeof(dp)); cin >> N >> M1; if (N == 0) break; M = M1 * 100; for (int i = 0; i < N; i++) { cin >> s >> d1; d = d1 * 100; for (int t = d; t <= M; t++) dp[t] = max(dp[t], dp[t - d] + s); } cout << dp[M] << endl; } return 0; }

https://www.acmicpc.net/problem/2662 풀이: dp[a][b]를 남은 금액이 a원 일 때, b번째 기업에 투자해서 얻을 수 있는 최대 이익이라고 하자. 첫번째 기업에 0원을 투자하는 것 부터 M번째 기업에 N원을 투자하는 것 까지 반복하여 최대 이익금을 구한다. 최대 이익금일 때 각 기업에 얼마를 투자했는지 구한 후 출력한다. 시간초과가 나기 쉬우므로 메모이제이션을 한다. 코드: 사용언어 : c++ 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 #include <iostream>#include <cstring>using namespace std; int N, M, s[302][22], dp[302][22], x[302][22]; int q(int a, int c) { if (c > M) return 0; int &m = dp[a][c]; if (m !

https://www.acmicpc.net/problem/1937 풀이: k[a][b]를 (a , b)지점에서 시작한 판다가 살아남은 최대 일수라고 한다. (a, b) 주변 십자가 방향 지점( (1,0), (-1, 0), (0, 1), (0, -1)) 에서 대나무의 양이 (a, b) 보다 낮다면 그 지점에 최대 일수에서 +1 한 값이 k[a][b] 값이 된다. 높은 값에서 낮은값으로 찾아가면서 최대 일수를 구한다. 시간초과가 날 수 있으므로 메모이제이션을 통해 시행횟수를 제한해준다. 코드: 사용언어 : c++ 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 #include <iostream>#include <algorithm>using namespace std; int n, s[510][510], k[510][510]; int dx[] = { 1,0,0,-1 }; int dy[] = { 0,1,-1,0 }; int panda(int a, int b){ for (int y = 0; y < 4; y++) if (a + dy[y] >= 0 && a + dy[y] < n && b + dx[y] >= 0 && b + dx[y] < n) if (s[a][b] < s[a + dy[y]][b + dx[y]]) { if(k[a + dy[y]][b + dx[y]] == 1) k[a][b] = max(k[a][b], panda(a + dy[y], b + dx[y]) + 1); else k[a][b] = max(k[a][b], k[a + dy[y]][b + dx[y]] + 1); } return k[a][b]; } int main(void) { cin >> n; int m = 1; fill(&k[0][0], &k[n][n], 1); for (int i = 0; i < n; i++) for (int t = 0; t < n; t++) cin >> s[i][t]; for (int i = 0; i < n; i++) for (int t = 0; t < n; t++) m = max(m, panda(i, t)); cout << m << endl; return 0; }

https://www.acmicpc.net/problem/5069 풀이: s[n][t][y]를 n번 이동해서 (t, y)인 방으로 다시 돌아오는 경우의 수라고 한다. 처음 상근이가 있는 방을 (10, 10)이라고 한다(n의 최대 수가 14 이므로 10칸을 넘어가지 않기 때문에) s[n][10][10] 은 n번 이동해서 상근이가 있는 방으로 돌아와야하므로 상근이의 근처에 있는 모든 n-1번 이동하여 돌아오는 경우의 수들의 합과 같다. 즉 s[n][10][10] = s[n-1][10][11] + s[n-1][10][9] + s[n-1][11][11] + s[n-1][11][10] + s[n-1][9][9] + s[n-1][9][10] 코드: 사용언어 : c++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <iostream>using namespace std; int s[15][21][21]; int dy[] = { 0,0,1,1,-1,-1 }; int dx[] = { 1,-1,1,0,-1,0 }; int main(void) { int T, a; cin >> T; s[0][10][10] = 1; for (int i = 1; i < 15; i++) for (int t = 1; t < 21; t++) for (int y = 1; y < 21; y++) for (int u = 0; u < 6; u++) if (t + dx[u] > 0 && t + dx[u] < 21 && y + dy[u] > 0 && y + dy[u] < 21) s[i][t][y] += s[i - 1][t + dx[u]][y + dy[u]]; while (T--) { cin >> a; cout << s[a][10][10] << endl; } return 0; }