백준 1720번 : 타일 코드
흔히 보던 타일 문제여서 쉬운 이겠거니 하고 덤볐다가 의외로 어려워서 쩔쩔맸던 문제... dp만 주구장창 풀어도 아직도 어렵다. 이 문제는 좌우 대칭이 아닌 경우를 세는 문제로 보이지만 역설적이게도 좌우 대칭인 경우를 세야한다. 글로 써놓고 보니까 단순히 여집합의 관계니까 그 정도 발상은 쉬운 거 아니냐 싶겠지만 나도 그렇고 이 문제로 검색을 해보면 많은 사람들이 이 발상이 어려웠다고 한다. 발상의 전환을 잘 기억해두도록 하자.
풀이
dp의 정의는 이런 타일 방식의 문제에 자주 쓰던 그 방식이다.
dp[n] : 길이가 n인 판(2 ×n)을 주어진 타일(1×2, 2×1, 2×2)로 채울 수 있는 경우의 수
dp는 대칭을 고려하지 않고 일반적이게 잡는다.
dp를 구하는 방법
이 dp를 구하는 점화식은 어렵지 않기 때문에 짧게 설명하려고 한다. 길이 n짜리 판의 마지막을 세로로 긴 1×2로 채운다면 나머지 n-1짜리 판을 채우는 방법은 dp [n-1]이다. 다른 방법으로 마지막을 가로로 긴 2×1 두 개나, 2×2 하나로 채운다면 나머지 n-2짜리 판을 채우는 방법은 dp[n-2]이다.
dp[n] = dp[n-1] + dp[n-2] × 2
답을 구하는 방법
뒤집었을 때 겹치지 않는 경우는 애초에 좌우 대칭인 경우이다. 이 개념이 약간 이상하게 느껴질 수도 있는데 생각해보면 맞다. 뭐라고 더 설명할 길이 없으니 이해가 잘 안 된다면 곰곰이 생각해보도록 하자.... 현재 dp에 존재하는 경우들은 두 가지로 나눌 수 있다.
- 자체적으로 좌우 대칭인 경우
- 자체적으로 좌우 대칭이지 않은 경우
2번의 경우 뒤집었을 때 다른 누군가와 겹치게 된다. 그 경우에는 하나로 취급한다고 했으므로 절반으로 나눠줘야 한다. 그러면 우리가 구하고자 하는 타일 코드의 개수는 다음과 같다.
Answer = (2번 / 2) + 1번
이때 1번의 경우의 수와 2번의 경우의 수를 합친 것이 dp[n]이므로 '1번 + 2번 = dp[n]'이라는 식을 이용해 식을 변형하면 이렇게 된다.
Answer = (dp[n] + 1번) / 2
dp는 이미 구했으므로 1번의 경우의 수만 구하면 된다.
자체적으로 좌우 대칭인 경우를 구하는 방법
n이 짝수인가 홀수인가에 따라 다르다. 먼저 홀수인 경우 좌우 대칭이기 위해서는 중간에 1×2가 반드시 들어가야 한다. 그리고 그 타일을 기준으로 왼쪽과 오른쪽이 좌우 대칭인 같은 형태의 타일이 들어가야 하므로 경우의 수는 dp[(n-1)/2]이다. 그다음으로 짝수인 경우는 완전히 절반으로 나누는 경우인 dp[n/2]와 중간에 2×1 두 개가 들어가거나 2×2 한 개가 들어가는 경우인 dp[n/2 - 1]이 있다.
홀수 : dp[(n-1)/2]
짝수 : dp[n/2] + dp[n/2 - 1] × 2
#include <iostream>
using namespace std;
int n;
int dp[32];
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= 30; i++)
{
dp[i] = dp[i-1] + dp[i-2] * 2;
}
if(n % 2 == 1)
{
cout << (dp[n] + dp[(n-1)/2])/2 << "\n";
}
else
{
cout << (dp[n] + dp[n/2] + dp[n/2 - 1] * 2)/2 << "\n";
}
return 0;
}