[JAVA] 백준 1904번 - 01타일

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		int dp[] = new int[1000001];
		
		dp[1] = 1;
		dp[2] = 2;
		
		for (int i = 3; i <= 1000000; i++) {
			dp[i] = (dp[i-1] + dp[i-2])%15746;
		}
		
		int N = sc.nextInt();
		
		System.out.println(dp[N]);
	}
}

 

👨🏻‍💻 결과

 

 

📕 풀이 방법

 

DP[N]

=

DP[N-2]

+

DP[N-1]

 

크기가 N인 타일을 만들기 위해서는

크기가 N-1인 타일 뒤에 "1"을 붙이고,
크기가 N-2인 타일 뒤에 "00"이나 "11"을 붙여서 만들 수 있습니다.

따라서 단순히 생각했을 때 DP[N] = DP[N-1] + 2*DP[N-2]가 정답인 듯 보입니다.

하지만 크기가 N-2인 타일 뒤에 "11"을 붙여 넣는 경우의 수는
이미 크기가 N-1인 타일 뒤에 "1"을 붙여 넣는 경우의 수에 포함되어 있으므로 

정답은 DP[N] = DP[N-1] + DP[N-2]이 됩니다.

 

그냥 단순하게 값을 구하여 규칙을 살펴볼 때
값들이 피보나치수열의 형태를 띠고 있어 어렵지 않게 풀이할 수 있는 문제였습니다.

 

 

🔗 링크

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

1904번: 01타일