BOJ 1904 - 01타일

문제

BOJ 1904 - 01타일

길이 N인 이진 수열을 만들 수 있는 경우의 수를 구하는 문제이다. 사용할 수 있는 타일은 00 (길이 2)와 1 (길이 1) 두 종류이다. 수열의 경우의 수가 매우 클 수 있으므로 15746으로 나눈 나머지를 출력한다.

입력

• 첫 번째 줄: 정수 N (1 이상 1,000,000 이하)

출력

길이 N인 이진 수열의 경우의 수를 15746으로 나눈 나머지를 출력한다.

예제

풀이

길이 N인 수열의 마지막에 오는 타일에 따라 점화식이 수립된다. 1로 끝나면 나머지 길이는 N-1이고, 00으로 끝나면 나머지 길이는 N-2이므로 f(N) = f(N-1) + f(N-2)로 피보나치 수열과 동일한 구조이다.

1. 기저 조건: N=1이면 1, N=2이면 2이다.
2. N이 3 이상인 경우 반복문으로 f(i) = f(i-1) + f(i-2) 계산을 진행한다.
3. 각 단계에서 15746으로 나머지 연산을 수행해 오버플로우를 방지한다.
4. 롤링 변수 t1, t2만 유지하여 O(1) 공간으로 구현한다.

핵심 아이디어: 00 타일 하나 또는 1 타일 하나를 추가하는 방식으로 나누면 피보나치 수열의 점화식이 성립한다. N이 최대 100만이므로 배열 없이 변수 2개만 롤링하여 공간을 절약한다.

코드

package com.ssafy.an.day049;
 
import java.util.Scanner;
 
public class Day48BOJ1904공일타일 { // 1904 01타일
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
 
		int ans = 0;
		int t1 = 1, t2 = 2;
		if(N == 1) ans = 1;
		else if(N == 2) ans = 2;
		else for(int i = 2 ; i < N ; i++) {
			ans = (t1 + t2) % 15746;
			t1 = t2;
			t2 = ans;
		} // 피보나치 수열의 모양이 된다는 것을 손코딩으로 확인하고 시작하기
		System.out.println(ans);
		sc.close();
	}
}

복잡도

• 시간: O(N) — N까지 선형 순회
• 공간: O(1) — 롤링 변수 t1, t2만 사용