[알고리즘 / 백준] 1904 - 01타일

www.acmicpc.net/problem/1904

1904번: 01타일

 

문제는 위와 같으며 이 문제의 경우 작은 단위로 쪼개다 보면 피보나치 수열의 규칙을 따른다는 것을 알 수 있습니다.

n 의 크기를 가지는 타일의 조합은 (n - 1) 크기의 타일에 1을 추가하거나 (n - 2) 크기의 타일에 00을 추가하는 방법 밖에 없기 때문에 이를 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2] 로 피보나치 수열과 일치합니다.

 

수열을 직접 반환하는 것이 아닌 만들 수 있는 수열의 개수를 출력하는 것이기 때문에 보다 쉽게 문제를 해결할 수 있습니다.

 

또한 동적 프로그래밍을 사용하여 작은 단위의 문제의 값을 메모리에 저장해서 나중에 큰 문제에서 사용할 때 다시 계산하지 않고 미리 구한 값을 가져와서 사용하는 방식으로 진행합니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n = int(stdin.readline())
result = [1 for _ in range(n + 1)]

for i in range(2, len(result)):
    result[i] = (result[i - 1] + result[i - 2]) % 15746  # 나중에 나머지를 구하는 경우 메모리 초과가 발생하므로 미리 나머지를 저장하는 방식으로 구현

print(result[n])

 

자바 코드는 다음과 같습니다.

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

public class BJAlgo_1904 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int[] result = new int[n + 1];
        result[0] = 1;
        result[1] = 1;

        for (int i = 2; i < result.length; i++) {
            result[i] = (result[i - 1] + result[i - 2]) % 15746;
        }

        System.out.println(result[n]);
    }
}