728x90
https://www.acmicpc.net/problem/2133
문제
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
입력
첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.
출력
첫째 줄에 경우의 수를 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
int N;
int dp[31];
int main(void){
cin >> N;
dp[1] = 0;
dp[2] = 3;
dp[3] = 0;
dp[4] = 11;
for(int i=5; i<=N; ++i){
if(i %2 == 1){
dp[i] = 0;
}
// 전 타일의 끝지점 집중
else{
for(int j = 3; j <= i/2; ++j){
dp[i] += dp[i-(j-1)*2]*2;
}
dp[i] += dp[i-2]*3 + 2;
}
}
cout << dp[N];
}
꽤 까다로운 dp 문제이다.
3*N의 타일을 채우는데 내가 생각한 관점과 구글에 올라온 관점이 달라 두가지 모두 설명해볼려 한다.
첫번째 관점은, 타일의 끝부분에 집중하는 것이다.
마지막에 오는 타일의 종류에 따라 점화식이 결정된다.
예를들어, 3*4 타일을 채울 때, 3*2 타일을 채우는 방식 3가지가 끝에올 수 있기 때문에 dp[i-2]*3 에다가 3*4를 채우는 특별한 모양 2가지를 더해 11가지가 된다. (특별한 모양에 대한 그림은 링크로 첨부하겠다.)
또, 3*6타일을 채울 땐 3*4때와 마찬가지로 dp[i-2]*3에다가 3*4를 채울 때 쓴 특별한 모양 2가지로 인해 dp[i-4]*2를 더해주고 또 특별한 모양 2가지가 나오니 2를 더한다. 그래서 dp[i-2]*3 + dp[i-4]*2 +2를 해주어 41가지가 된다.
이 점화식을 일반화 해서 세운 코드가 위의 코드이다.
또 구글링해서 찾은 방식은 다르다. 내가 생각한 관점보다 더 명확한거 같다.
경우의 수를 이용한 방식인데 설명하면 너무 기니 링크를 첨부하겠다.
https://yabmoons.tistory.com/536
이 분이 경우의 수를 이용해 잘 설명하신 것 같다.
728x90
반응형
'PS > DP' 카테고리의 다른 글
[2225] 합분해 (4) | 2023.07.18 |
---|---|
[14501] 퇴사 (0) | 2023.07.03 |
[2294] 동전 2 (0) | 2023.06.27 |
[11054] 가장 긴 바이토닉 부분 수열 (0) | 2023.04.29 |
[11053] 가장 긴 증가하는 부분 수열 (0) | 2023.04.16 |