https://www.acmicpc.net/problem/2133
문제의 설명이 매우 단순하니만큼 시뮬레이션을 돌려봐야 할 거 같다는 생각이 들었다.
dp[i] = 3 * i 크기의 벽을 타일로 채우는 경우의 수
로 가정하고, 차근차근 N = 1부터 진행해보자.
풀이
N = 1
2 * 1과 1 * 2의 타일로는 3 * 1을 채울 수 없다.
즉 dp[1] = 0
N = 2
로 총 3가지의 모양이 나온다.
즉 dp[2] = 3
N = 3
역시 타일을 채울 수 없었다.
여기까지 했으면 N에 홀수가 들어갈경우 dp배열의 값이 0이라는 걸 추측이 가능하다.
N = 4
중앙을 기준으로 나눴을 때, dp[2] * dp[2] = 9라는 걸 알 수 있다.
그럼 dp[4] = 9인걸까???
답은 아니다이다.
문제의 힌트를 유심히 보면
4칸짜리에 특수한 모양이 있다.
이 모양을 생각하면 2를 추가로 더해줘야 한다.
즉 dp[4] = dp[2] * dp[2] + 2 = 11이 된다.
N = 5(생략)
N = 6
3 * 6을
3 * 4 와 3 * 2의 결합된 형태로 보면
dp[4] * dp[2]를 통해 경우의 수로 구할 수 있다.
그럼 이게 끝일까?
.
.
.
아니다!!!
3 * 2와 3 * 4의 결합된 형태도 존재한다.
그럼 dp[2] * dp[4]를 한 번 더 더해줘야 되는구나~~
할 수 있지만,,,
3 * 4는 3 * 2와 3 * 2로 또 나눌 수 있으므로,
사실 위에서 구한 경우의 수와 중복된 형태가 많이 존재할 것이다.
그럼 다 중복인건가??? 싶지만
dp[4]를 구할 때 봤듯이 4칸짜리 특수한 모양이 두 개 존재한다.
즉, dp[2] * 2를 더해줘야 되는 것이다.
그럼 dp[6] = dp[4] * dp[2] + dp[2] * 2네!
라고 넘어가선 안된다.
N = 4의 경우와 마찬가지로
N = 6의 경우도 6칸짜리 특수한 모양이 2개 존재한다.
그래서 dp[6] = dp[4] * dp[2] + dp[2] * 2 + 2이다.
여기까지 했으면 대략 규칙이 감이 잡힐테지만 한 번만 더 해보도록 하자.
N = 8
3 * 8은
3 * 6과 3 * 2, 3 * 4와 3 * 4, 3 * 2와 3 * 6, 그리고 3 * 8으로 경우의 수를 나눌 수 있다.
1. 3 * 6과 3 * 2
= dp[6] * dp[2]로 쉽게 구할 수 있다.
2. 3 * 4와 3 * 4는
dp[4] * dp[4]이 아니라는 것을 N = 6에서 확인할 수 있었다.
중복된 경우의 수가 굉장히 많을 것이다.
3 * 4 하나가 특수한 모양을 띨 때, 3 * 6과 3 * 2의 경우에서 없는 경우일 것이다!!!
즉, dp[4] * 2이다.
3. 3 * 2와 3 * 6
역시나 중복된 것을 제외하면 3 * 6이 특수한 모양일 때만 남을 것이다!!
즉, dp[2] * 2이다.
4. 3 * 8
특수한 모양을 생각해보면 2이다.
이 값들을 다 더하면 dp[8] = dp[6] * dp[2] + dp[4] * 2 + dp[2] * 2 + 2 이라는 걸 알 수 있다!
점화식 구하기
dp[2] = 3
dp[4] = dp[2] * dp[2] + 2
dp[6] = dp[4] * dp[2] + dp[2] * 2 + 2
dp[8] = dp[6] * dp[2] + dp[4] * 2 + dp[2] * 2 + 2
나열해보니 규칙이 확실히 보인다.
dp[n] = dp[n-2] * dp[2] + dp[n-4] * 2 + dp[n-6] * 2 + ... dp[0] * 2
(dp[0] = 1이라고 했을 때)
점화식까지 구했으니 코드로 구현만 하면 된다!
전체 코드
#include <iostream>
#include <algorithm>
using namespace std;
int dp[34];
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
dp[0] = 1;
dp[2] = 3;
for(int i = 4; i <= n; i+=2){
dp[i] = dp[i-2] * dp[2];
for(int j = i-4; j >= 0; j -= 2){
dp[i] += dp[j] * 2;
}
}
cout<<dp[n];
return 0;
}
dp[0]과 dp[2]에 초기값을 넣는 것만 주의해서 코드를 짜면 성공적으로 AC를 맞을 것이다.
'알고리즘 별 문제 정리 > DP' 카테고리의 다른 글
[C++] 백준 17070: 파이프 옮기기 1 (0) | 2024.07.18 |
---|---|
[C++] 백준 2565: 전깃줄 (0) | 2024.07.17 |
[C++] 백준 2225: 합분해 (1) | 2024.07.14 |
[C++] 백준 2294: 동전 2 (0) | 2024.07.14 |
[C++] 백준 1520: 내리막 길 (1) | 2024.07.13 |