https://www.acmicpc.net/problem/2618 풀이: DP[i][t] : 첫번째 경찰차가 i 번째 사건을, 두번째 경찰차가 t 번째 사건을 처리했을 때, 이동하는 거리의 합의 최소값 i 와 t 의 차이가 1 이라면, DP[i][t] = DP[i][0 ~ t - 1] (t 번째와 0 ~ t - 1 번째 사이의 거리)까지의 최소값 1이 아니라면, DP[i][t] = DP[i][t - 1] + (t 번째와 t - 1 번째 사이의 거리) 을 통해 최솟값을 구할 수 있다. 최솟값을 구한 후, 최솟값을 구한 경로를 역순으로 추적하여, 맡겨진 경찰차의 번호를 구한다.

https://www.acmicpc.net/problem/2667 풀이: 전체를 순회한다. 만약 집이있는 곳 ( 배열에 1인 곳 ) 을 찾았다면, 연결된 모든 단지를 찾아 단지 크기를 배열에 저장한다. 순회가 끝났다면, 배열의 사이즈 (총 단지수) 를 출력한다. 그 후 단지내 집의 수를 오름차순으로 정렬하여 출력하여야하므로 배열을 정렬한 후 배열의 원소를 출력한다. 코드: 사용언어 : 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 35 36 37 #include <iostream>#include <vector>#include <string>#include <algorithm>using namespace std; int n; bool b[26][26]; vector<string> a; vector<int> c; void num(int x, int y) { b[x][y] = true; c.

https://www.acmicpc.net/problem/10816 풀이: 배열에 숫자 카드들을 넣는다. 배열을 정렬한다. 몇 개 가지고 있는지 구해야 할 카드를 k 라고 할 때, k가 최초로 나오는 위치 = lower_bound, k보다 큰 값이 최초로 나오는 위치 = upper_bound 로 구할 수 있다. 즉 upper_bound - lower_bound를 실행한다면 답을 구할 수 있다. cout과 cin 을 쓰면 시간초과가 나므로 주의하자. 코드: 사용언어 : c++ 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 n, m, k, a[500001]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); scanf("%d", &m); for (int i = 0; i < m; i++) { scanf("%d", &k); auto l = lower_bound(a, a + n, k); auto r = upper_bound(a, a + n, k); printf("%d ", r - l); } printf("\n"); return 0; }

https://www.acmicpc.net/problem/11049 풀이: DP[i][t] : i ~ t 까지의 행렬을 곱하는데 필요한 곱셈 연산 횟수의 최솟값 dp[x][y] = min(dp[x][y], f(x, i) + f(i + 1, y) + a[x] * b[i] * b[y]) x ~ i 까지의 행렬 곱셈 + (i + 1) ~ y 까지의 행렬 곱셈 + 그 둘의 곱셈 코드: 사용언어 : c++ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <iostream>#include <algorithm>using namespace std; long long n, a[502], b[502], dp[502][502] = {}; long long f(int x, int y) { if (x == y || dp[x][y]) return dp[x][y]; dp[x][y] = f(x, x) + f(x + 1, y) + a[x] * b[x] * b[y]; for (int i = x + 1; i < y; i++) dp[x][y] = min(dp[x][y], f(x, i) + f(i + 1, y) + a[x] * b[i] * b[y]); return dp[x][y]; } int main() { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i] >> b[i]; cout << f(1, n) << endl; }

https://www.acmicpc.net/problem/11066 풀이: dp[i][t] = i 장 부터 t 장까지 수록한 파일을 합쳤을 때, 필요한 최소비용 sum[i] = 1 ~ i 까지의 파일 크기의 합 dp[i][t] = min(dp[i][t], dp[i][i] ~ dp[i][t - 1] + dp[i + 1][t] ~ dp[t][t]) 로 구할 수 있다. 겹치는 숫자들이 있으므로, dp를 구할 때 마다, dp[i][t] += sum[t] - sum[i - 1] 을 해주어야 한다. 코드: 사용언어 : 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 #include <iostream>#include <algorithm>using namespace std; int T, n, a[502], dp[502][502] = {}, sum[502]; int f(int a, int b) { if (dp[a][b] !

https://www.acmicpc.net/problem/11286 풀이: 0이 나온다면, 배열에 있는 값중 절댓값이 가장 작은 값을 출력한다.(절댓값이 같다면, 가장 작은 값을 출력한다.) 그 값을 배열에서 제외시킨다. 만약 배열이 비어있다면, 0을 출력한다. 0이 아닌 다른 숫자가 나온다면, 그 값을 배열에 넣는다. cout, cin 을 사용하면, 시간초과가 나므로 주의하자. 코드: 사용언어 : 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 #include <iostream>#include <queue>using namespace std; int n, i, m; bool com(int a, int b) { if (abs(a) == abs(b)) return a > b; return abs(a) > abs(b); } int main() { priority_queue<int, vector<int>, decltype(&com)> a(&com); scanf("%d", &n); for (i = 0; i < n; i++) { scanf("%d", &m); if (!