백준 1720 타일 코드 Kotlin (dp)

문제 출처 : https://www.acmicpc.net/problem/1720

1720번: 타일 코드

문제

2×N 크기의 넓은 판을 1×2 (또는 2×1) 크기와 2×2 크기의 타일로 채우려고 한다. 여러 가지 경우가 있을 수 있으므로, 각각을 하나의 코드로 대응시켜서 암호화에 이용하려고 한다.

그런데 문제가 생겼다. 넓은 판을 교환하다 보니 좌우 대칭인 경우가 있어, 뒤집히는 경우 코드가 헷갈리게 되는 경우가 발생한 것이다. 예를 들어 아래의 두 경우는 달라 보이지만 좌우 대칭을 이루고 있다.

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

입력

첫째 줄에 타일의 크기 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 타일 코드의 개수를 출력한다.

알고리즘 분류

• 수학
• 다이나믹 프로그래밍
• 조합론

풀이

백트래킹을 이용한 조합 문제 풀려고 들어왔다가 메모리 초과 뚜드려 맞고 dp로 푼 문제.

무지성으로 짜지 말고 조건을 잘 읽자!

 

2021.09.22 - [알고리즘 문제 풀이/백준] - 백준 11727 2xn 타일링 2 c++ (dp)

이전 타일 문제의 응용 버전이다.

 

모든 타일을 구하는 점화식은 어렵지 않다. (사실 이것도 쉽지 않다. dp 점화식은 항상 생각하기 어려워)

위의 글을 읽고 온다면, 좌우 대칭을 신경쓰지 않고 구한 모든 타일의 점화식은

dp[i] = dp[i-1] + dp[i-2]*2

라는 것을 알 수 있다.

왜 이렇게 되는지 간략하게만 설명한다면, i까지의 경우의 수는 i-1의 경우에서 2*1(세로 타일)을 하나 추가하는 경우 +

i-2의 경우에서 1*2(가로 타일)을 두 개 추가하는 경우 + 2*2(정사각형 타일)을 한 개 추가하는 경우이기 때문이다.

 

우선 문제에서 예시로 든 좌우대칭을 살펴보자.

2*1 타일을 a

2*2 타일을 b

1*2 타일을 c

라고 할 때, 정방향은 abac

역방향은 caba이다.

위에서 구한 타일의 모든 경우는 abac와 caba 각각 다른 경우로 취급하였지만, 문제에선 이를 하나로 취급해야 한다.

여기서, aaaa도 당연히 좌우대칭이다. 하지만 이 경우는 뒤집었을 때 구조가 완전히 같은 경우로, 타일의 모든 경우에 하나만 들어가있다. 이를 완전한 대칭이라고 하겠다.

 

이젠 좌우 대칭인 경우를 빼줘야 한다. 이 부분이 문제의 핵심이다!!

약간의 아이디어가 필요한데, 그림... 하 또 그림을 그려야하는구나

n이 6이라고 할 때의 모습이다.

예를 들어 위와 같은 경우는 좌우대칭으로 한 번 빼줘야 한다.

위의 점화식에서 구한 모든 경우는 이러한 좌우대칭의 경우가 모두 들어가 있다.

하지만 위와 같은 경우도 좌우대칭이지만 거꾸로 뒤집어도 모양이 같은 것을 알 수 있다.

즉 모든 경우를 구했을 때, 좌우대칭인 하나씩 빼줘야 하지만, 애초에 이렇게 완전한 대칭은 하나씩만 들어가 있다.

 

여기서 조금 짱구를 굴리면 모든 경우 + 완전한 대칭 경우의 수를 하면, 모든 대칭에 대해 2번씩 들어간 모든 경우의 수를 알 수 있다.

모든 대칭이란 말이 조금 모호한데,

aa

ab

bb

가 있다고 하면

aa

ab

bb

aa

ba

bb

의 경우를 구했다고 생각하면 된다.

 

따라서 이 값에 2를 나누면 모든 경우를 조건에 맞게 한 번씩만 탐색한 경우의 수를 찾을 수 있다.

//n이 2인 경우 답이 2로 나오는 경우를 방지하기 위해 dp[0]에 1을 넣었다.

코드

val br = System.`in`.bufferedReader()

//1<=n<=30
fun main() = with(System.out.bufferedWriter()){
    val n = br.readLine().toInt()
    val dp = IntArray(31)
    dp[0] = 1
    dp[1] = 1
    dp[2] = 3
    for(i in 3 .. n){
        dp[i] = dp[i-1]+dp[i-2]*2
    }
    //짝수인 경우
    if(n%2==0){
        write("${(dp[n]+(dp[n/2]+dp[n/2-1]*2))/2}")
    }
    else{
        write("${(dp[n]+dp[n/2])/2}")
    }

    close()
}