(Kotlin) 백준 1904 - 01타일

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

1904번: 01타일

 

풀이)

사용할 수 있는 타일은 (1, 00) 2가지이다.

아마 모든 경우의 수를 생각해서 조건문으로 문제를 풀려고 하면 머리가 터질 것이다.

 

다이나믹 프로그래밍)

사실 이 문제는 다이나믹 프로그래밍으로 유명한 기본 문제인데, 나 역시 DP를 공부하려고 푼 문제다!ㅎㅎ

 

DP의 핵심 개념은 크게 2가지이다. 

1. 재귀적으로 생각한다. 즉, 작은 문제의 정답은 이미 구해졌다고 믿는다.

2. 불필요한 계산을 줄인다.

(서울대생 분께서 아주 친절하게 설명해주십니다: https://www.youtube.com/watch?v=2RwlzBDhGh4)

 

1번의 재귀적으로 생각한다는 것은 점화식을 구하는 것과 같다.

타일의 개수는 1)마지막에 반드시 1을 사용하는 경우와 2)반드시 00을 사용하는 경우 2가지로 나눌 수 있는데, 이게 모든 경우의 수를 커버한다.

이것을 점화식으로 표현하면, a(n) = a(n-1) + a(n-2), 초기값은 a(1) = 1, a(2) = 2이 되는데,

a(n)은 타일의 개수가 n일 때, 만들 수 있는 모든 2진수의 가짓수를 의미한다.

피보나치랑 같은 식이 나와서 뭐지? 싶었는데 어이없게도 이게 맞다.

 

2번의 불필요한 계산을 줄이는 건, 탑다운 방식으로 풀 때는 메모이제이션 방식을, 바텀업 방식에서는 배열에 값을 저장해서 같은 문제의 답을 다시 구하지 않도록 해주면 된다.

 

이제 이것을 코드로 작성하면 놀랍도록 짧은 코드가 나오게 된다.

 

코드)

fun main(){
    val n = readLine()!!.toInt()
    val dp = IntArray(1_000_001)	// 크기 n+1로 설정하면, n=1일 때 인덱스 에러 생겨요ㅠㅠ
    dp[1] = 1; dp[2] = 2

    for (i in 3..n){
        dp[i] = (dp[i-2] + dp[i-1]) % 15746 // 점화식
    }
    
    println(dp[n])
}

 

리뷰)

• 처음에 배열 크기를 n+1로 하면, n=1일 때 인덱스 에러로 틀릴 수 있다.
• 맞아요 그게 저에요.