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 문제 자체는 쉬운데.. 문제를 잘못 읽어서 엄청 고생했다. 정수 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:..

Approach 기본적으로 다음 문제와 거의 비슷하다. https://viyoung.tistory.com/288?category=884242 [백준 15665번] [Backtracking] N과 M (11) Approach 중복된 숫자의 입력을 제거해주면, https://viyoung.tistory.com/284?category=884242 문제와 완벽히 동일하다. [백준 15656번] [Backtracking] N과 M (7) Approach 기본적인 접근 방법은 https://viyou.. viyoung.tistory.com 다만, 비내림차순이라는 조건때문에 함수 내부의 반복문에서 자기 자신의 index부터 고려해주면 된다. Code #include #define fastio ios_base::syn..

Approach 중복된 숫자의 입력을 제거해주면, https://viyoung.tistory.com/284?category=884242 문제와 완벽히 동일하다. [백준 15656번] [Backtracking] N과 M (7) Approach 기본적인 접근 방법은 https://viyoung.tistory.com/283.과 동일하다. [백준 15655번] [Backtracking] N과 M (6) Approach 문제에서 요구한 조건이 내림차순이라는 조건이 있으므로, 정렬한 상태에서 몇.. viyoung.tistory.com 중복된 것만 unique함수를 통해 지워주면 된다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), co..

Approach 기본적인 접근 방법은 다음 문제와 비슷하다. https://viyoung.tistory.com/286 [백준 15663번] [Backtracking / Map] N과 M (9) Approach 같은 숫자가 여러 개 들어갈 수 있음에도 불구하고, 중복되는 수열을 여러 번 출력하면 안되는 것이 이 문제의 가장 핵심이다. 이전 문제의 경우 단순히 해당 index 이후부터 고려하거나 처 viyoung.tistory.com 다만, 비내림차순이라는 조건때문에 함수 내부의 반복문에서 자신의 index 이상부터만 고려해준다는 점에서 차이점이 존재한다. Code #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) us..