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..

Approach 사실 문제에서 접근 방법을 다 제시해서 쉽게 풀 수 있다. 하노이의 탑 알고리즘의 경우 recursion만 잘 활용해주면 쉽게 풀 수 있다. hanoi[n] : 2 * hanoi[n - 1] + 1 for i $\ge$ 2 (Define that hanoi[1] is 1) dp[n] : min{hanoi[j] + 2 * dp[n - j]} for $ 1 \le j \le n$ (Define that dp[1] is 1) Code #include #define fastio ios_base::sync_With_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int hanoi[13]; int dp[13]; int hanoi_cal(int n){..

Approach 한 글자가 숫자에 하다씩 매핑되는 양상이므로 replace 등의 함수를 활용하는 것이 아니라, ASCII를 활용하여 대문자와 주어진 숫자를 하나씩 매핑해주는 방식을 사용해주면 된다. 추가적으로 계산이 초기 문자열의 길이 * 2 - 1 부터 시작해서 1개씩 줄어드는 양상이고, 처리 순서가 앞에서 뒤로만 가고 있으므로 큐 자료구조를 활용해주면 쉽게 처리할 수 있다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace std; int dp[26] = {3, 2, 1, 2, 3, 3, 2, 3, 3, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 2, 1, 1, 1..

Approach 문제 자체는 쉬운데.. 문제를 잘못 읽어서 엄청 고생했다. 정수 k개를 더해서 합이 N이 되는 경우의 수를 구하는 상황이다. 그런데, 정수 k - 1개를 고른 상황에 대한 정보를 알면 구하고자 하는 경우의 수를 알 수 있는 느낌을 충분히 받을 수 있다. 이 지점에서 관계식을 포현할 수 있음을 인식하고, DP를 통해 이 문제를 해결할 수 있다는 것을 파악했으면 충분하다. 관계식 자체는 되게 단순하다. dp[i][j] : 정수 i개를 사용해서 합이 j가 되는 경우의 수 dp[i][j] = $\sum\limits_k dp[i - 1][j - k]$ for $0\ge k \ge j$ (단, i가 1일때의 dp[i][j] = 1이고 dp[i][0] = 1로 항상 고려해주면 된다.) 특이 케이스들에..

Approach 특정한 조건에 의해서 경향성이 결정지어지는 것을 보고 점화식을 통해 방법의 수를 찾을 수 있을 것이라는 느낌을 받을 수 있다. 다만 (N, N)으로 뻗어나가는 방향으로는 판단하기가 어려운데, 왜냐하면 뻗어나가는 것은 이전 파이프의 상태로 가로/세로/대각 여부에 따라 달라지기 때문이다. 따라서 DP를 해당 좌표를 기준으로 들어오는 것을 기준으로 점화식을 세워주면 된다. dp[i][j][0~3] : (i, j)에서 0~3번의 방향으로 들어오는 경우의 수 (단, 0은 대각선, 1은 세로, 2는 가로 방향) 추가적으로 들어오는 것을 기준으로 판단하고 있는 상황이므로, Top-down 방식을 활용하면 좋다는 것을 알 수 있다. (Bottom-up 방식은 다음 블로그를 참고하도록 하자. https:..