백준 비요뜨의 징검다리 건너기(18291)

비요뜨의 징검다리 건너기

1. 힌트

1) $f(x) =$ $x$번 위치에서 $N$번째 징검다리에 정확하게 도착하는 경우의 수로 정의할 수 있습니다.

2) $f(x) = \displaystyle\sum_{k=x+1}^{N}f(k)$입니다.

3) $f(N)$부터 거꾸로 계산하면서 수열을 직접 만들어보면 규칙을 찾을 수 있습니다.

2. 접근

1) 뒤에서부터 생각해서 문제를 풀 수 있을까?

힌트 3)에서처럼 뒤에서부터 직접 수열을 만들어보면 다음과 같습니다
$16,\ 8,\ 4,\ 2,\ 1,\ 1$
뒤에서 두 번째 항부터 $2$배씩 증가하고 있음을 알 수 있습니다. $2$의 거듭제곱은 $O(N)$으로 단순히 구현할 수 있지만 $N$의 범위가 크므로 분할정복을 이용해서 구현합니다. $2^x = 2 \times 2^{x-1}$임을 이용합니다.
$2^{x-1}$을 한 번 계산해놓으면 거기에 $2$를 곱해서 사용하면 되므로 이 경우 시간 복잡도는 $O(lgN)$입니다.

3. 구현

import java.io.*;
import java.util.*;

public class Main {
	static final int MOD = 1000000007;
	
	// 2의 n승 반환
	static long pow(int n) {
		if (n == 0) return 1;
		if (n % 2 == 0) {
			long ret = pow(n / 2);
			return ret * ret % MOD;
		} else {
			return 2 * pow(n - 1) % MOD;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		int TC = Integer.parseInt(br.readLine());
		while (TC-- > 0) {
			int N = Integer.parseInt(br.readLine());
			int ret = 0;
			if (N <= 2) {
				ret = 1;
			} else {
				N -= 2;
				ret = (int)pow(N);
			}
			bw.append(ret);
			bw.append("\n");
		}
		System.out.print(bw);
	}

}

1) 시간 복잡도

$O(lgN)$