[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p149)
이 문제는 앞선 포스트에서도 재귀적 방법으로 풀어 본적이 있는 문제이다. 그러나 숫자가 커짐에 따라 기하급수적으로 계산량이 늘어날 수 있으므로, 여기서는 가장 효율적인 방법으로 접근해 보려고 한다. 책에서도 점화식을 n, n-1, n-2 사이의 관계와 n과 n/2사이의 관계를 설명하고 있다. 지금까지 문제 풀이 방법으로 보았을때, 상향식 동적 계획법 (Dynamic Programming)이 가장 빠른 접근 방법이나 책에서는 보여주지 않고 있다. 따라서 이 방법을 풀이해 보고자 한다.
중요한 것은 점화식을 유도해 내는 과정을 잘 이해하는 것이라고 생각된다.
1) n이 짝수이면, 절반씩 나눠 채우는 방법과 1칸씩을 내어논 상태에서 채운 다음 2칸을 채울 수 있는 2가지 방법을 곱한다.
2) n이 홀수이면, 절반씩 나눠 채우는 방법 (한쪽이 다른쪽보다 1칸 더 김), 나눈 2부분에서 1칸씩 내어놓고 내어놓은 2칸을 채우는 2가지 방법을 곱한다.
import java.util.Scanner;
public class FillTiles149 {
public static int n, m;
public static int[] DT = new int[100001];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
sc.close();
// 초기값을 3개까지 지정해 주어야 한다. 2개만 지정할 경우 아래에서 i가 3이면 DT[0]을 찾게된다.
DT[1]=1;
DT[2]=3;
DT[3]=5;
for (int i=4; i <=n; i++){
if (i%2==0){
DT[i]=(DT[i/2]*DT[i/2]+DT[i/2-1]*DT[i/2-1]*2)%m;
}
else{
DT[i]=(DT[i/2]*DT[i/2+1]+DT[i/2]*DT[i/2-1]*2)%m;
}
}
System.out.println(DT[n]);
return;
}
}
Big O(log n)
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/FillTiles149.java