[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, 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

문제해결을 위한 창의적 알고리즘 목록