[백준] 1904번 : 01타일(JAVA)

Dynamic Programming Master가 되어보자

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

1904번: 01타일

위의 문제는 BaekJoon Online Judge의 단계별로 풀어보기 중 14단계

 

동적 계획법 1의 카테고리에 포함되어 있는 문제이다.

 

길이가 증가할 때마다 2진 수열의 개수도 늘어난다.

 

1, 2, 3, 5, 8, ...

 

식을 구해보면 A(n) = A(n-2) + A(n-1)이라는 식이 나오게 된다.

 

A(n)은 A(n-2)의 값에 00타일을 붙이고 A(n-1)의 값에 1타일을 붙이는 경우로 계산한다.

 

예). A(3)의 값 : A(1)의 값인 1에 00을 붙임 = 100, A(2)의 값인 00과, 11에 1을 붙임 = 001, 111

 

A(3) = 100, 001, 111

 

출력을 보면 수열의 개수를 15746으로 나눈 나머지를 출력한다고 나와있다.

 

문제의 핵심은 나머지를 나중에 하면 숫자의 범위가 초과된다는 것이다.

 

N의 자리수가 1,000,000까지인데 저 수열의 항이 100번째만 되어도 수가 기하 급수적으로 늘어나기 때문에

 

나는 계산하면서 바로바로 나머지연산을 해주었다.

 

import java.util.Scanner;

public class Question_1904 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		
		int[] Cal = new int[N+1];
		
		Cal[1] = 1;
		if(N != 1)
			Cal[2] = 2;
		
		for(int i = 3; i < N + 1; i++) {
			Cal[i] = (Cal[i-2] + Cal[i-1])%15746;
		}
		System.out.println(Cal[N]);
	}
}