와 나 이거만 하고 자려고 했는데 이거 63쪽짜리야 pdf 와와 미쳤나봐 와와 나 자고싶은데 와와
그래도 내가 강의를 듣고 와볼게 하나 둘 셋 얍
듣고 온 후기 : DP는 점화식 싸움이고 이번강의 문제 짱많고 하기싫고 지금 새벽 4시인거 너무 서럽고 나 내일 9시에 일어날거고... 일단 들었으니까 자고 내일 9시에 일어나서 마저하고 수강신청할거야 뿌에엥 ㅠㅠ
----------------------------------------------------------------------------------------------------------------------------------
<15988번 / 1, 2, 3 더하기 3>
기존 1, 2, 3 더하기 문제에서 n의 범위만 커짐
|
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; #define MAX 1000001 long long d[MAX]; #define mod 1000000009 int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; d[0] = 1; d[1] = 1; d[2] = 2; d[3] = 4; while (t--) { int n; cin >> n; for (int i = 4; i <= n; i++) { d[i] = (d[i - 1] + d[i - 2] + d[i - 3]) % mod; } cout << d[n] << '\n'; } return 0; } |
cs |
<1149번 / RGB 거리>
사람들 집에 RGB중 하나로 칠하려고 하는데 이 때 이웃은 같은 색으로 칠할 수 없다. 이것도 연속조건이 있으므로 집 i의 색깔을 j라고 하면 i-1번째 집과 i+1번쨰 집은 j를 제외한 두 가지 색깔로 칠할 수 있다.
>D[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최소값
j=0 -> 빨강 / j=1 -> 초록 / j=2 -> 파랑 이라고 한다. 그리고 A[i][j]를 i번째 집을 j색으로 칠하는데 드는 최소비용이라고 하면 j가 0, 1, 2일때로 나눠서 점화식을 세울 수 있다.
D[i][0] = min(D[i-1][1] + D[i-1][2]) + A[i][0]
D[i][1] = min(D[i-1][0] + D[i-1][2]) + A[i][1]
D[i][2] = min(D[i-1][1] + D[i-1][0]) + A[i][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 28 29 30 31 32 33 34 35 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 1001 long long d[MAX][MAX]; long long a[MAX][MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = 0; j < 3; j++) { cin >> a[i][j]; } } d[0][0] = d[0][1] = d[0][2] = 0; d[1][0] = a[1][0]; d[1][1] = a[1][1]; d[1][2] = a[1][2]; for (int i = 2; i <= n; i++) { for (int j = 0; j < 3; j++) { d[i][0] = min(d[i - 1][1], d[i - 1][2]) + a[i][0]; d[i][1] = min(d[i - 1][0], d[i - 1][2]) + a[i][1]; d[i][2] = min(d[i - 1][0], d[i - 1][1]) + a[i][2]; } } cout << min(d[n][0], min(d[n][1], d[n][2])) << '\n'; return 0; } |
cs |
<1309번 / 동물원>
가로 두 칸, 세로 N칸인 동물원에 동물 배치하는 방법, 단 가로 세로로 붙어있게 배치하면 안된다.
그러면 각 가로에 대해서 동물을 놓는 경우에 대해 생각한다. 아래에서 3번은 서로 연속하기 때문에 0~2번까지만 가능한 경우다.
위를 통해 점화식을 세우면 다음과 같다.
아니 왜 그냥 더하면 틀리고 9901로 나눈 나머지를 더한건 맞는거지?? 수가 너무 커서 그런가?? long long으로 선언했는데?? 이게 어차피 9901로 나눈 나머지가 들어가야 하는건가?? 진짜 이해 안가네...뭐지
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 100001 long long d[MAX][3]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; d[0][0] = d[0][1] = d[0][2] = 0; d[1][0] = d[1][1] = d[1][2] = 1; for (int i = 2; i <= n; i++) { d[i][0] = (d[i - 1][0] + d[i - 1][1] + d[i - 1][2]) % 9901; d[i][1] = (d[i - 1][0] + d[i - 1][2]) % 9901; d[i][2] = (d[i - 1][0] + d[i - 1][1]) % 9901; } cout << (d[n][0] + d[n][1] + d[n][2]) % 9901 << '\n'; return 0; } |
cs |
<11057번 / 오르막 수>
계단수와 비슷한 문제.
D[i][j] = 길이가 i이고 마지막 숫자가 j인 오르막 수의 개수
D[1][i] = 1이다.
마지막 숫자가 j라고 하면, 그 앞의 수는 뭐가 올지 모르니까 변수 k라고 둔다. 그러면 k는 0~j까지의 숫자가 오면 되고 k를 구하는 방법은 D[i-1][k]가 된다. 이 떄 모든 경우의 수를 구하는 거니까 D[i-1][k]를 모두 더해준다.
D[i][j] += D[i-1][k] (0<=k<=j)
정답 구할 떄 n까지의 모든 배열 더해주어야 한다.
|
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 <algorithm> using namespace std; #define MAX 1001 long long d[MAX][MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < 10; i++) { d[1][i] = 1; } for (int i = 1; i <= n; i++) { for (int j = 0; j < 10; j++) { for (int k = 0; k <= j; k++) { d[i][j] += d[i - 1][k]; d[i][j] %= 10007; } } } long long res = 0; for (int i = 0; i < 10; i++) { res += d[n][i]; } cout << res % 10007 << '\n'; return 0; } |
cs |
<9465번 / 스티커>
이 문제는 동물원과 비슷하게 풀면 된다. 다만 동물원은 경우의 수여서 모든 경우의 수를 다 더해줬지만 이 문제는 최댓값이기 때문에 최대값만을 구해주면 된다. 이것도 세로로 나눠서 위, 아래, 안 뜯는 경우로 나눠서 풀면 된다.
D[i][j] = 2*i에서 얻을 수 있는 최대 점수, i번 열에서 뜯는 스티커는 j 라고 한다. 그럼 다음과 같이 점화식을 세울 수 있다.
그려 동물원이랑 비슷하게 구현하세여~
|
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 <algorithm> using namespace std; #define MAX 100001 long long d[MAX][3]; long long a[MAX][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; for (int j = 0; j < 2; j++) { for (int i = 1; i <= n; i++) { cin >> a[i][j]; } } d[1][0] = 0; d[1][1] = a[1][0]; d[1][2] = a[1][1]; for (int i = 2; i <= n; i++) { d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2])); d[i][1] = max(d[i - 1][0], d[i - 1][2]) + a[i][0]; d[i][2] = max(d[i - 1][0], d[i - 1][1]) + a[i][1]; } cout << max(d[n][0], max(d[n][1], d[n][2])) << '\n'; }
return 0; } |
cs |
<2156번 / 포도주 시식>
이건 이친수랑 똑같다고 설명도 안해주더라 해봅시당~
이 때 포도주는 연속으로 3번 마실 수 없으니까 3번 연속 조건을 하기위해서 변수를 사용한다.
D[i][j] = A[1], ..., A[i] 까지 포도주를 마셨을 때, 마실 수 있는 포도주의 최대 양, A[i]는 j번 연속해서 마신 포도주이다.
그러면 j로 경우를 나눠서 생각할 수 있다.
-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 28 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 10001 long long d[MAX][3]; long long a[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } d[1][0] = 0; d[1][1] = a[1]; d[1][2] = 0; for (int i = 2; i <= n; i++) { d[i][0] = max(d[i - 1][0], max(d[i - 1][1], d[i - 1][2])); d[i][1] = d[i - 1][0] + a[i]; d[i][2] = d[i - 1][1] + a[i]; } cout << max(d[n][0], max(d[n][1], d[n][2])) << '\n'; return 0; } |
cs |
이건 1차원 다이나믹으로도 풀 수 있다.
D[i] = A[1], ..., A[i]까지 포도주를 마셨을 때, 마실 수 있는 포도주의 최대 양이라고 한다.
위의 경우에는 D[1]과 D[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 28 29 30 31 32 33 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 10001 long long d[MAX]; long long a[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } d[1] = a[1]; d[2] = a[1] + a[2]; for (int i = 3; i <= n; i++) { d[i] = d[i - 1]; //마시지 않는 경우 if (d[i] < d[i - 2] + a[i]) { d[i] = d[i - 2] + a[i]; } if(d[i] < d[i - 3] + a[i] + a[i - 1]) { d[i] = d[i - 3] + a[i] + a[i - 1]; } } cout << max(d[n - 1], max(d[n - 2] + a[n], d[n - 3] + a[n] + a[n - 1])); return 0; } |
cs |
<1932번 / 정수 삼각형>
(i, j)를 i행 j열 숫자라고 생각하자. 아래층으로 내려올 때는 대각선 왼쪽 또는 대각선 오른쪽에 있는 것만 선택할 수 있따. 그러면 내려오기 전 수를 생각해주면 된다. 어떤 수가 선택되기 전에 선택된 수는 대각선 왼쪽위 또는 오른쪽 위에 있는 것이다. D[i][j]를 i행 j열이 선택되었을 때 최대합이라고 하면, (i,j)가 선택되기 전에 선택된 수는 (i-1,j), (i-1, j-1) 중 하나다. 따라서 점화식은 다음과 같다.
> D[i][j] = max(D[i-1][j], D[i-1][j-1]) + A[i][j]
|
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; #define MAX 501 long long d[MAX][MAX]; long long a[MAX][MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { cin >> a[i][j]; } } d[1][1] = a[1][1]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { d[i][j] = max(d[i - 1][j], d[i - 1][j - 1]) + a[i][j]; } } cout << *max_element(d[n], d[n] + MAX) << '\n'; return 0; } |
cs |
<11055번 / 가장 큰 증가하는 부분 수열>
LIS와 비슷하게 풀면 된다. LIS가 길이를 구하는 문제였다면 이는 합을 구하는 문제이다. 이것도 변수 추가해서 이차원 다이나믹으로 풀어주면 된다.
D[i] = A[1], ..., A[i]까지 수열이 있을때, A[i]를 마지막으로 하는 가장 큰 증가하는 부분 수열의 합
그럼 얘는 LIS 코드에서 d[i]의 초기값을 1이 아닌 a[i]로 초기화하고, 항의 개수가 아니기 때문에 1이 아니라 a[i]를 더해준다.
마지막에 답 구할때 얘도 max를 출력해줘야 한다. d[n]이 항상 최댓값이 아니니깐!
|
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; #define MAX 1001 long long d[MAX]; long long a[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { d[i] = a[i]; for (int j = 0; j < i; j++) { if (a[j] < a[i] && d[i] < d[j] + a[i]) { d[i] = d[j] + a[i]; } } } cout << *max_element(d,d+MAX) << '\n'; return 0; } |
cs |
<11722번 / 가장 긴 감소하는 부분 수열>
얘는 LIS랑 같다.
진짜 똑같네 부등호 방향만 바꿔주었따
|
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; #define MAX 1001 long long d[MAX]; long long a[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { d[i] = 1; for (int j = 1; j <= i; j++) { if (a[j] > a[i] && d[i] < d[j] + 1) { d[i] = d[j] + 1; } } } cout << *max_element(d, d + MAX) << '\n'; return 0; } |
cs |
이거 말고도 반복문을 역으로 추적하여 구현할 수 있는데 이건 다음문제 풀때 좋으니까 해봅시다
<11054번 / 가장 긴 바이토닉 부분 수열>
바이토닉 수열은 특정 원소까지 증가하다가 그 원소에서 다시 감소하는 수열을 말한다. 이를 풀기 위해서는 수열 2개를 이용한다. 수열을 2개로 나눠서 i번째까지 증가한는 수열과 i번째 부터 감소하는 수열로 설정한다.
증가구하고 감소구하고 d[i]+d2[i]-1이 큰 값을 찾으면 된다~ 1빼주는 이유는 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 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 1001 long long d[MAX]; long long d2[MAX]; long long a[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { d[i] = 1; for (int j = 1; j <= i; j++) { if (a[j] < a[i] && d[j] + 1>d[i]) { d[i] = d[j] + 1; } } } for (int i = n; i >= 1; i--) { d2[i] = 1; for (int j = i + 1; j <= n; j++) { if (a[i] > a[j] && d2[i] < d2[j] + 1) { d2[i] = d2[j] + 1; } } } int res = 0; for (int i = 1; i <= n; i++) { if (res < d[i] + d2[i] - 1) { res = d[i] + d2[i] - 1; } } cout << res << '\n'; return 0; } |
cs |
<13398번 / 연속합2>
이건 이전 연속합 문제와 달리 수 하나를 제거할 수 있다. 이 문제는 바이토닉 아이디어를 이용하여 풀어볼 수 있다. 만약 하나씩 지워보면서 다 구하면 기존 연속합 문제의 시간복잡도가 O(N), 변수 개수는 N개이므로 총 O(N^2)이 걸려서 너무 오래걸린다. 그래서 배열을 두 개로 나눠서 구해보려고 한다. DL[i]를 i번째에서 끝나는 연속합, DR[i]를 i번째에서 시작하는 연속합이라고 하자. 만약 k번째 수를 지우면 D[k-1]과 D[k+1]만 영향을 받기 때문에 이렇게 구해도 된다. (k 지우면 k-1, k+1이 연속하니까) 따라서 DL[i-1] + DR[i+1]이 i번째 수를 제거했을 때 i번째 수가 포함되는 최대 연속합이 된다.
뭐지 이거 max_element로 하면 틀리고 왜 배열로 최댓값 반복문으로 구현하니까 맞았지? 뭐지 이거????왜지???? 질문 올려봐야겠다.
-> 이거 답이 음수면 max_element에서 배열 초기화 값이 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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 100001 long long dl[MAX]; long long dr[MAX]; long long a[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } for (int i = 0; i < n; i++) { dl[i] = a[i]; if (i == 0) continue; if (dl[i] < dl[i - 1] + a[i]) { dl[i] = dl[i - 1] + a[i]; } } for (int i = n - 1; i >= 0; i--) { dr[i] = a[i]; if (i == n - 1) continue; if (dr[i] < dr[i + 1] + a[i]) { dr[i] = dr[i + 1] + a[i]; } } int res = dl[0]; for (int i = 1; i < n; i++) { if (res < dl[i]) res = dl[i]; } for (int i = 1; i < n - 1; i++) { if (res < dl[i - 1] + dr[i + 1]) res = dl[i - 1] + dr[i + 1]; } cout << res << '\n'; return 0; } |
cs |
<2133번 / 타일 채우기>
이번엔 3*n을 채우는 방법의 수이다. D[i] = 3*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; long long d[31]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; d[0] = 1; d[2] = 3; d[4] = 11; int j; for (int i = 6; i <= n; i++) { d[i] = 3 * d[i - 2]; j = i - 4; while (j >= 0) { d[i] += 2 * d[j]; j -= 2; } } cout << d[n] << '\n'; return 0; } |
cs |
으아아아ㅏ 다해써ㅓ어어어
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 1강 브루트 포스 - 건너 뛰며 해보기 (0) | 2020.08.28 |
|---|---|
| 1강 브루트 포스 - 브루트 포스 (0) | 2020.08.27 |
| 4강 다이나믹 프로그래밍 1 - 합분해까지 (0) | 2020.08.24 |
| 4강 다이나믹 프로그래밍 1 - 이친수까지 (0) | 2020.08.22 |
| 4강 다이나믹 프로그래밍 1 - 1, 2, 3 더하기까지 (0) | 2020.08.22 |
댓글