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

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로 항상 고려해주면 된다.) 특이 케이스들에..