[ BOJ 백준 1720번 - 타일 코드 ] 해설 및 코드

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

 

 

목적

N이 주어지면, 전체 타일 코드의 개수를 구하는 프로그램을 작성하시오. (단, 서로 좌우 대칭을 이루는 중복된 표현은 한 가지 경우로만 처리한다.)

 

접근법

1. N이 4일 때, 좌우 대칭을 이루는 표현을 포함하여 나올 수 있는 타일 코드는 다음과 같다.

 

2. 타일의 모양을 살펴보면, 좌우 대칭(색칠된 타일)인 타일과 좌우가 같은 타일 두가지 경우로 나타난다. 좌우가 같은 타일은 아래 그림과 같은 타일들이다. 이와 같이 좌우 대칭인 타일을 X, 좌우가 같은 타일을 Y라고 할 때, 총 2X+Y개의 타일이 만들어 진다. 문제에서 좌우 대칭인 타일을 하나의 경우로 처리하는 것이므로 좌우 대칭인 타일을 없애야 한다. 하지만 그러한 타일을 찾기는 어렵다...(누군가에겐 쉬울지도) 좌우가 같은 타일 Y를 2X+Y에 더해서 2로 나누는 방법으로 X+Y를 구한다.

 

3. s[i]를 가로가 i일때의 경우의 수라고 하면, 좌우가 같은 타일은 대략 s[i/2]라고 생각할 수 있을 것이다. 더 정확하게는 이를 i가 홀수인 경우와 짝수인 경우로 나누어 생각해야 한다.

• 홀수인 경우는 가운데에 1x2타일을 두고 좌우가 같은 타일들의 경우가 Y에 해당하므로 s[i/2]이다.
• 짝수인 경우는 가운데에 2x(1 or 2)타일을 두고 좌우가 같은 경우 2*s[i/2-1]과 사이에 아무 타일이 없는 경우 s[i/2]를 더한 값이다. s[i/2] + 2*s[i/2-1]는 s[i/2+1]로 표현 가능하다.

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
 
int s[31]={0,1,3};
 
int sol(){
    int n;cin>>n;
    if(n==1)return 1;
    f(i,3,n)s[i]=s[i-1]+(s[i-2]<<1);
    return (s[n]+(n&1?s[n>>1]:s[(n>>1) + 1]))>>1;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cout<<sol();
    return 0;
}
 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.