[JAVA/백준] 동적 계획법 1: 01타일

👀 문제

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

👊 도전

1. 설계

1. DP의 Bottom-Up 방식으로 이용한다.
2. Memorization 기법 사용을 위해 배열을 둔 뒤, 작은 문제부터 해결해내가며 값을 저장하고, 중복호출 시 메모리 값을 재활용한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;

/**
 * 
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int cnt=0;
		int[] array=new int[n+1];
		array[1]=1;
		array[2]=2;
		for(int i=3;i<=n;i++){
			array[i]=(array[i-1]+array[i-2])%15746;
		}
		System.out.println(array[n]);
	}
}
 

3. 결과

🤟 성공 🤟

4. 설명

1. DP의 Bottom-Up방식을 이용한다.
   • 배열을 이용하여 n일때 필요한 타일 수를 저장한다.
   • n=1이면 1만 만들 수 있고, n=2이면 2개 가능하다.
   • n=3이면 100, 001, 111 가능하므로 3개이다.
   • n=4이면 0000, 0011, 1100, 1111, 1000 5개이다.
   • 이를 통해 array[n]=array[n-2]+array[n-1]이라는 것을 알 수 있다(피보나치 공식과 같다).
   • 피보나치는 n=46일때 int형을 초과하지만, 값을 15746으로 나눈 나머지를 사용하므로 답이 int형을 벗어나지 않게 된다.

👏 해결 완료!

참고

• [백준 - 1904번] 01타일 - Java //Wello Horld// https://wellohorld.tistory.com/17
• [백준] 1904 - 01타일 http://blog.naver.com/PostView.nhn?blogId=occidere&logNo=220787441430