[백준] 1904 - 01 타일

백준 바로가기

1904번: 01타일

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

타일 문제는 가지고 있는 타일의 종류에 유의해서 풀어야 되나 봅니다. 그런 다음 어떤 원리가 있는지 규칙을 찾아야 합니다. 일일이 경우의 수를 손으로 구해가며 규칙을 찾으려 하다 경우의 수를 하나라도 빠뜨리면 틀린 규칙이 되버리기 때문입니다. 제가 그랬듯이...

원리에 입각한 풀이방법으로 설명하자면 우리가 가진 타일은 '00' 또는 '1' 두 가지 입니다. 그리고 n번째 경우의 수는 n-2와 n-1 번째 경우의 수에 각각 '00'과 '1' 타일을 추가해 모든 경우의 수를 더한다는 원리를 이해하면 점화식은 쉽게 도출됩니다. 

왜 경우의 수를 따로 구하지 않냐고 물어보시면 재귀 개념을 한번 풀어보시는 것을 추천드립니다. 이미 n-1, n-2번째 경우의 수는 (n-1)-1, (n-2)-1,...., 1, 0 까지 진행된 결과물입니다. 따라서 n번째 경우의 수는 n-1번째, n-2번째 경우의 수만 더하면 됩니다. 숟가락만 얹는거죠, 반복문에 의해 이전 경우의 수는 모두 구해졌으니까요.

또는 n-2번째에 '00' 타일을 추가하고 n-1번째에 '1'타일을 추가하는 게 왜 n번째 경우의 수인지 궁금하다면 손으로 직접 6번째 경우의 수까지 적어보는 것을 추천드립니다. 저도 알고리즘 문제를 풀 때 한번에 이해되는 경우가 적은 편이라 원리를 이해하기 까지 펜을 사용해 푸는 스타일입니다.

동적계획법의 기저엔 재귀가 자리하고 있기 때문에 basecase로 배열 dp[1], [2] (index 1,2)에는 숫자를 넣어줍니다.

아 그리고 답을 제출해도 '런타임 에러'가 뜨는 경우가 있는데 arrayIndexOutofBound거나 데이터 타입이 long이 아닌 int라 그럴 수 있으니 주의해주세요!

package baekJoon.week12;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Tile01_1904 {
 
    static int n;
    static long[] dp;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
 
        dp = new long[n + 2];
        dp[1] = 1;
        dp[2] = 2;
 
        if (n >= 3) {
            for (int i = 3; i <= n; i++) {
                dp[i] = (dp[i - 2] + dp[i - 1]) % 15746;
            }
        }
 
        System.out.println(dp[n]);
    }
 
}