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

동적 계획법(DP)을 공부한 뒤, DP관련 문제인 1904번 : 신나는 함수 실행을 풀었다.

 

 

동적 계획법에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/23

[알고리즘] 동적 계획법 (Dynamic Programming)

 

바로 이전, 동적 계획법 관련 문제는 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/25

[백준] 9184번 : 신나는 함수 실행 (JAVA)

 

---

<문제>

 

<문제 해석>

동적계획법(DP)을 이용하여 타일의 갯수(N)이 주어질 때, 만들수 있는 타일의 갯수를 구하라.

 

타일은 0, 1로만 이루어져있고 0타일은 2개를 붙인 00한쌍으로만 이용할 수 있다.

 

 

 

 

<문제 해결>

이번 문제도 규칙만 찾으면 쉽게 해결할 수 있는 동적 계획법 문제였다.

 

규칙을 찾기위해서 N=1일때부터 만들 수 있는 타일의 갯수를 세보았다.

 

 

N의 갯수	만들 수 있는 타일의 종류					갯수
N = 1	1					1
N = 2	00, 11					2
N = 3	001, 100, 111					3
N = 4	0000, 0011, 1001, 1100, 1111					5
N = 5	00001, 00100, 00110, 00111, 10011, 11001, 11111					8
N = 6	000000, 000011, 001001, 001100, 001111, 100100, 100111, 110011, 100001, 110000, 111001, 111100, 111111,					13

 

 

위의 표를 아래와 같은 식으로 나타낼 수 있다.

P(1) = 1

P(2) = 2

P(3) = 3

P(4) = 5

P(5) = 8

P(6) = 13

 

 

 

자세히 보면 아주 익숙한 피보나치 수열 규칙을 따른다는 것을 알 수 있다.

• P(N) = P(N-1) + P(N-2)

 

따라서 피보나치 수열을 적용하여 N이 주어질 때, 만들 수 있는 타일의 갯수를 구할 수 있다.

 

 

 

 

<코드>

import java.io.IOException;
import java.util.Scanner;

public class Main {	
	
	static int dp[];
	
	public static void main(String[] args) throws IOException {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		dp = new int[1000001];
		
		System.out.println(fibo(n));
	}
	
	static int fibo(int n) {
		
		dp[0] = 0;
		dp[1] = 1;
		dp[2] = 2;
		
		if(dp[n] == 0) {
			dp[n] = (fibo(n-2) + fibo(n-1)) % 15746;
		}
		return dp[n];
	}
	
	
}

 

 

---

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

1904번: 01타일