[BOJ/백준][Gold5] 1720 : 타일 코드 (C++)

https://www.acmicpc.net/problem/1720

1720번: 타일 코드

 

 

[난이도] Gold5
[유형] DP

[풀이]
DP[i] = DP[i-1] + DP[i-2]*2 점화식을 이용해 모든 코드의 개수를 구할 수 있습니다.

이미 좌우 대칭인 코드를 제외한 모든 코드는 자신과 대칭이 되는 코드를 가지고 있습니다.
이미 좌우 대칭인 코드의 개수를 t라고 했을 때,
최종 정답은 (DP[N]-t)/2 + t 가 됩니다.
그 이유는 DP[N]-t 가 자신과 대칭이 되는 코드를 가지고 있는 코드들의 개수이므로
중복 제거를 위해 이것을 2로 나누어 주면 중복이 제거되기 때문입니다.
여기에 다시 좌우 대칭인 코드의 개수인 t를 더해줌으로써 최종 답이 됩니다.

t를 구하는 방법은 홀수와 짝수인 경우가 달라집니다.
홀수인 경우 좌우 대칭이려면 가운데 무조건 2x1 타일이 있어야 하므로
t = DP[N/2] 가 됩니다.

짝수인 경우에는 중앙에 2x1 타일 두개, 2x2 타일 한개가 위치하고, 이를 중심으로 대칭인 경우도
추가해 주어야 하므로
t = DP[N/2] + 2*DP[N/2-1] 이 됩니다.

 

#include <cstdio>
int N,dp[31];
int main(){
    scanf("%d",&N);
    dp[1]=dp[0]=1;
    for(int i=2;i<=N;i++) dp[i]=dp[i-1]+dp[i-2]*2;
    int t=dp[N/2];
    if(N%2==0) t+=2*dp[N/2-1];
    printf("%d",(dp[N]-t)/2+t);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1720.cpp