[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p35)

이 문제에서 익혀야 할 핵심은 점화식을 만들때, n번째 항과 n-1번째 항과의 관계식을 구하는 것이 아니라, n번째 항과 n/2번째 항과의 관계를 구하는 방법이다. 이를 통해 굉장히 효율적인 점화식을 만들 수 있기 때문이다. 특히 n이 홀수일 때와 n이 짝수일 때를 점화식을 유도하는 방법을 잘 익히는 것이 필요해 보인다.

import java.util.Scanner;

public class FillTilesSol45 {

public static int n;

public static int m;

public static long f(int k) {

if (k<=1)

return 1%m;

// k가 홀수일 

else if (k%2>0)

return (f(k/2)*f(k/2+1)+2*f(k/2)*f(k/2-1))%m;

// k가 짝수일 때

else

return (f(k/2)*f(k/2)+2*f(k/2-1)*f(k/2-1))%m;

}

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

n = sc.nextInt();

m = sc.nextInt();

sc.close();

System.out.println(f(n));

return;

}

}

Big O(log n) (n은 타일 길이)

GitHub: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/FillTilesSol45.java

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