백준: 타일 채우기, 타일링 ①(2133, 1720)
오랜만에 문제 풀이다
중간고사 때부터 종강하고 지금까지 쉬었다가 이제 다시 시작한다
타일 문제들은 거의 비슷하다 그림만 잘 그리면 된다 그게 좀 어렵긴 하지만…
기본적인 경우(2*N)
2*N
크기 벽을 2*1
, 1*2
, 2*2
타일로 채우는 경우의 수를 보자
대충 이런 그림이 될 거다
2*1
타일에 2*(n-1)
을 붙이거나, 2*2
타일에 2*(n-2)
을 붙이거나, 1*2 + 1*2
타일에 2*(n-2)
을 붙이는 경우다.
이 때 겹치지 않게 경우를 나누는 게 중요하다.
AB ***
AB ***
예를 들어 위 경우는 1번 경우와 겹쳐지기 때문에 추가하면 안 된다.
dp 식으로 표현하면
dp[n] = dp[n-1] + 2 * dp[n-2];
이 된다.
2133: 타일 채우기
https://www.acmicpc.net/problem/2133
문제: 3*N
크기 벽을 2*1
, 1*2
타일로 채우는 경우의 수
1번 경우와 2번 경우로 나눌 수 있다
물론 이 때도 겹치지 않게 경우를 나누도록 조심해야 한다. 1번에서 나눠가지고 2번으로 가보니 똑같은 경우가 있다던가 하면 안 된다
2번은 그림을 보면 알겠지만 총 칸의 수가 2 + 3*(n-1)
이기 때문에 n이 홀수일 때만 가능하고 짝수일 땐 경우의 수가 0이 된다(총 칸의 수가 짝수가 아니므로).
따라서 점화식도 dp2[n-1]
을 dp2[n-2]
로 적었다. 어차피 똑같음
#include <bits/stdc++.h>
using namespace std;
int dp[31];
int dp2[31];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
if( n % 2 ){
cout << 0 << endl;
return 0;
}
dp[2] = 3;
dp2[1] = 1;
dp2[3] = 4;
for(int i = 4; i <= n; i++){
dp2[i-1] = dp[i-2] + dp2[i-3];
dp[i] = dp2[i-1] * 2 + dp[i-2];
}
cout << dp[n] << endl;
}
식은 뭐 걍 그대로 짜면 됨
1720: 타일 코드
https://www.acmicpc.net/problem/1720
문제: 2*N
크기 벽을 2*1
, 1*2
, 2*2
타일로 채우는데, 좌우 대칭인 경우 뺀 경우의 수
맨 처음 보았던 기본적인 경우에서 좌우 대칭인 것들을 생각해 보자
파란색 동그라미는 좌우 대칭되는 다른 짝이 없는 거고, 각 주황색 도형들은 좌우 대칭되는 짝들이다.
이렇게 보니 그 타일링 자체가 좌우 대칭이면 다른 짝이 없고, 그게 아니면 다 짝이 있게 된다. 생각해 보면 당연함
해서 타일링 자체가 좌우 대칭이 되는 경우를 세어 보자
양 옆에 2*1
타일이 붙은 경우나, 2*2
타일이 붙은 경우나, 1*2 + 1*2
타일이 붙은 경우가 있다.
따라서 기존 dp에는 타일링 자체가 좌우대칭인 것들
과 좌우대칭이 되는 짝들
이 섞여 있으므로,
(좌우대칭이 되는 짝들) = dp[n] - (타일링 자체가 좌우대칭인 것들)
ans = (좌우대칭이 되는 짝들) / 2 + (타일링 자체가 좌우대칭인 것들)
로 구하면 될 거 같다.
dp[1] = 1;
dp[2] = 3;
for(int i = 3; i <= n; i++){
dp[i] = dp[i-1] + dp[i-2] * 2;
}
dp2[0] = 1;
dp2[1] = 1;
dp2[2] = 3;
dp2[3] = 1;
for(int i = 4; i <= n; i++){
dp2[i] = dp2[i-2] + dp2[i-4] * 2;
}
cout << (dp[n] - dp2[n]) / 2 + dp2[n] << endl;
코드도 뭐 그대로…
베이스 케이스가 0에서 1이 되어야 한다.
만약 0이 될 경우 이전 단계에서 딱 맞게 떨어져서 0으로 넘어 왔을 때의 경우를 체크하지 못하게 된다.
길어서 잘라서 올려야 겠넹
댓글남기기