알고리즘
[문제해결을 위한 창의적 알고리즘] 타일 채우기 (고급, p35)
nevermet
2016. 9. 16. 19:13
이 문제에서 익혀야 할 핵심은 점화식을 만들때, 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은 타일 길이)