백준 비요뜨의 징검다리 건너기(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$

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)$