Approach 이 문제를 보고 그리디 문제라고 오해하기 쉬우나, 2원과 5원의 최대공약수가 1이므로 단순히 큰 숫자를 더 많이 가져가는 식의 접근 방법이 통하지 않는다. dp[i] : minimum number of constructing i(Won) using 2 and 5 Therefore dp[i] = min(dp[i - 2], dp[i - 5]) + 1 (Base case : dp[2] = 1, dp[5] = 1) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[100001]; int main(void){ fastio; memset(dp, -1, ..

Approach https://viyoung.tistory.com/292 와 완전히 유사하다. [백준 15312번] [동적 계획법] 이름 궁합 Approach 한 글자가 숫자에 하다씩 매핑되는 양상이므로 replace 등의 함수를 활용하는 것이 아니라, ASCII를 활용하여 대문자와 주어진 숫자를 하나씩 매핑해주는 방식을 사용해주면 된다. 추가적으 viyoung.tistory.com Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; string a, b; cin >> a >> b; queue q; for(int i = 0; i ..

Approach 주어진 문장인 "welcome to code jam"의 순서를 지키면서 몇 개 만들 수 있는지가 목표이므로, 각 알파벳이 등장할 때 주어진 문장에서 어느 부분까지를 활용할 수 있는지를 체크해주면 된다. Let define dp[i] : 주어진 i번째 index까지를 만들 수 있는 subsentence의 수 Suppose that input value is x, dp[k] += dp[k - 1] for every k s.t x == dp[k]. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[19]; int main(void){ fastio;..

Approach 한 점을 기준으로 가능한 경우는 2가지 밖에 없다. 현재 방향으로 이동 현재 방향에서 오른쪽으로 이동 잘 생각해보면, 전자의 경우는 행이 주는 경우이고 후자의 경우는 열이 주는 경우이다. 그리고 바라보는 방향은 크게 중요하지는 않은데 왜냐하면 대칭이기 때문이다. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] (if i or j == 1, dp[i][j] = 1) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int main(void){ fastio; int t; cin >> t; long long dp[26][26]; memse..

Approach Consonant와 vowel 사이의 관계식이 주어진 상황이므로 DP를 활용하여 풀 수 있음을 직감적으로 느끼면 된다. DP 식 자체는 다음과 같다. dp[i + 1][0] = dp[i][1] * c dp[i + 1][1] = (dp[i][0] + dp[i][1]) * v (0은 consonant, 1은 vowel) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; long long dp[16][2]; // regard of x + 0 : consonant, 1 : vowel int c, v, l; int main(void){ //자음 뒤 무조건 모음 i..

Approach https://viyoung.tistory.com/295 문제와 완벽히 동일하다. [백준 9655번] [동적 계획법] 돌 게임 Approach 최선의 선택을 한다는 사실을 잘 생각해보면, 결과적으로 최소한의 움직임만 고려해주면 된다. 가장 최소한의 움직임에서 움직임이 늘어나는 경우는 3이 선택되어야하는 상황에 1을 선택 viyoung.tistory.com 다만, 마지막에 돌을 둔 사람이 지는 것이므로 승자만 바꿔주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[1001]; int n; int dp_value(int x) { if ..

Approach 최선의 선택을 한다는 사실을 잘 생각해보면, 결과적으로 최소한의 움직임만 고려해주면 된다. 가장 최소한의 움직임에서 움직임이 늘어나는 경우는 3이 선택되어야하는 상황에 1을 선택하는 상황인데, 최적 상황에서의 우승자는 1을 유지해주면 마지막에 고르는 것이 그대로 유지된다. 따라서, 최소한의 선택으로 N개를 분배하는 방법을 찾고 선택의 횟수가 홀수이면 SK, 짝수이면 CY를 출력해주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[1001]; int n; int dp_value(int x){ if(x < 1) return 987654..

Approach 움직일 수 있는 방향이 고정되어 있는 상황이므로 관계식을 쓸 수 있다는 점만 캐치했다면 동적 계획법 풀이를 바로 떠올릴 수 있다. dp[i][j] : max(dp[i + 1][j], dp[i][j - 1]) + value[i][j] (이때, index가 grid 범위를 넘는 경우에는 0) Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int value[7][7]; int dp[7][7]; int n; int dp_value(int x, int y){ if(x = n || y >= n) return 0; else ret..