[ 백준 1904 ] 01타일 ( Java )

 

문제 링크

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

1904번: 01타일

문제 풀이

점화식 문제이고, 동적 프로그래밍 방법을 알면 쉽게 풀 수 있는 문제입니다.

차근차근 a1부터 써보면 값을 예측할 수 있습니다.

a1 = 1;

a2 = 2;

a3 = a1 + a2 = 3;

a4 = a2 + a3 = 5;

...

 

어떻게 이렇게 나오게 되는지 알아보겠습니다.

예를들어 a5의 경우를 보겠습니다.

 

1. a5는 맨 앞에 00이 오거나 1이 오게 됩니다.

2-1. 00이 오게되면 나머지 3자리는 a3와 같은 수열로 채워집니다.

2-2. 1이 오게되면 나머지 4자리는 a4와 같은 수열로 채워집니다.

3. a3+a4를 하게되면 a5의 값을 구할 수 있습니다.

 

이문제는 단순 재귀로 풀게되면 시간이 너무 오래 걸리기 때문에 동적 프로그래밍을 사용해야 합니다.

그리고, 탑다운 방식(재귀)으로 풀게 되면 스택오버플로우가 나기 때문에 바텀업 방식(반복문)을 이용하여 푸는 것이 쉽습니다.

 

 

소스 코드

import java.util.*;
public class Main {
	static long [] memo;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		memo = new long[n+1];
		for (int i = 0; i <= n; i++) {
			if( i ==0 || i ==1 || i==2) memo[i] = i;
			else memo[i] = (memo[i-1] + memo[i-2])%15746;
		}
		System.out.println(memo[n]);
	}
}