[Kotlin, S3] 백준 1904번 01타일

출처: unsplash.com

 

01타일(1904번)

Silver 3

#다이나믹 프로그래밍

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

 

문제 내용

 

 

문제 접근

타일의 구성이 00, 1로 총 2가지가 존재한다. 타일들로 구성해야 하는 자릿수가 N일 때 타일 2종류를 무한대로 사용해서 자릿수가 N인 수를 만들어야 한다.

문제 설명에서처럼 N이 4일 때는 0011, 0000, 1001, 1100, 1111 총 5가지의 경우의 수가 존재한다.

 

먼저 N의 개수에 따라 경우의 수가 몇 개인지 일일이 세서 알아내 보자.

사진 1-1

위의 표는 자릿수(N)에 따른 00, 1로 나타낼 수 있는 N자리의 수들을 나열한 것이다.

어떤 규칙이 보이게 된다.

바로 피보나치수열과 동일한 규칙으로 개수가 증가하는 것을 볼 수 있다.

N이 3이 될 때부터 피보나치수열을 구할 때처럼 바로 뒷자리의 개수와 두 번째 뒷자리의 개수의 합으로 구성된다.

그렇게 되면 점화식은 다음과 같이 구성할 수 있다.

array[i] = (array[i - 1] + array[i - 2]) % 15746

15746을 나누는 이유는 문제 설명에 언급되어 있다시피 총개수에 나머지를 출력해야 하기 때문에 15746을 나눈 나머지를 대입해 준다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val tileCnt = readLine().toInt()
    val array = Array(tileCnt + 1) { 1 }

    for (i in 2 .. tileCnt) {
        array[i] = (array[i - 1] + array[i - 2]) % 15746
    }

    println(array[tileCnt])
}

 

문제 풀이

타일의 총개수를 입력받고 각 자릿수의 타일의 개수를 저장할 array의 초기 데이터를 1로 설정한다.

그리고 2부터 시작해서 피보나치수열 구하듯이 위에서 언급한 점화식을 대입해서 마지막에 tileCnt번째 index의 값을 출력.

 

 

문제 해결 과정

다이나믹 프로그래밍 문제는 각 경우에 해당하는 답을 직접 찾아서 구해 보면 규칙 파악이 쉬워서 점화식을 쉽게 구할 수 있다.

정 힘들면 브루트포스로 구현해 보고 중복되는 데이터를 제거해 가는 방법으로 구현해 보라고 하던데, 아직까지는 잘 모르겠다. 여전히 어렵다 다이다믹 프로그래밍 문제는.