백준 1904 - 01타일 ( JAVA )

출처 - 백준 알고리즘

1904번: 01타일

---

 

알고리즘

{ 00, 1 } 을 사용하여 수열을 만들어야 할 때, 각 원소로 시작하는 수열을 만든다고 생각해보자. 

 

N= 1 일 경우, [1]

N= 2 일 경우, [00, 11] 

N= 3 일 경우, [001, 111, 100] 

N= 4 일 경우, [0000, 0011, 1001, 1100, 1111] 

... 

 

N의 값이 1, 2일 경우를 제외하고는 00으로 시작하는 수열의 갯수 + 1로 시작하는 수열의 갯수인 것을 알 수 있다. 

즉, N-2(=00) 길이의 수열 갯수 + N-1(=1) 길이의 수열 갯수 인 것이다. 

 

이전의 작은 값들(N-1, N-2)을 저장하여 하나의 큰 값(N)을 구하는 다이나믹 프로그래밍 DP 를 사용한다. 

길이가 N인 모든 2진 수열의 갯수를 dp[] int 형 배열에 저장 했을 때, dp[N] = dp[N-2] + dp[N-1] 이다. 

단, N 이 3 이상일 때만 !!

 

 

+ 신경써야 할 부분 

1.  dp에 저장하는 과정은 N= 3일 때 부터 저장하므로, N<3 일경우에는 런타임 에러에 주의 !! 

2.  각 길이에 대해 길이가 N 인 수열의 갯수를 15764 으로 나눈 나머지를 저장해야 한다. 

 

---

 

소스 코드 

import java.util.*;

public class Solution_BaekJoon_1904 {
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in); 
		int N= sc.nextInt(); // 지원이가 만들 수 있는 길이 
		
		int dp[] = new int[N+1];
		
		//런타임 에러 주의 ! 
		if(N<3) {
			System.out.println(N);
			return; 
		}
	
		dp[1] = 1; // N=1일때는 0: 1개
		dp[2] = 2; // N=2일때는 00, 11 : 2개 		
		for(int i=3; i<=N; i++) {
			dp[i] = (dp[i-1]+dp[i-2])%15746; 
		}

		System.out.println(dp[N]);
	}
}