[KOITP] 계단 오르기

출    처 : http://koitp.org/problem/SDS_PRO_7_6/read/

시간 제한	메모리 제한	제출 횟수	정답 횟수 (비율)	정답자 수
1.0 초	512 MB	1497	180 (12%)	162

문제

최대 2 칸 까지 오를 수 있을 때 오르는 방법의 가짓수를 생각해 보자.

아래 그림은 n 이 4 인 경우의 예 이다.

• 1 - 2 - 3 - 4
• 1 - 2 - 4
• 1 - 3 - 4
• 2 - 3 - 4
• 2 - 4

총 5가지 경우가 존재한다.

그렇다면 계단의 수가 n개일 때는 경우의 수가 몇가지 존재할까? 답이 커질 수 있으므로 답을 1,000,000,007로 나눈 나머지를 출력한다.

입력

입력의 첫 줄은 계단의 갯수 (1 <= N <= 1,000,000,000)이 주어진다.

출력

계단 N개를 오를 수 있는 경우의 수를 10억 7로 나눈 나머지를 출력한다.

힌트

예제 입력

4

예제 출력

5

< Comment >

 사실 다른 점화식으로도 풀 수 있지만, 처음 떠올리는 점화식으로는 시간 초과가 나기 쉽다고 합니다. 기본적으로 생각할 수 있는 점화식은 한번에 계단을 1칸 혹은 2칸 뛰어넘을 수 있으므로 D(n) = D(n-1) + D(n-2) 와 같은 식인데, 해당하는 방식으로는 조금 구하기 힘든 부분이 있습니다. 그러나 잘 살펴보면, {{1, 1}, {1, 0}} 배열을 n - 1 제곱해 주고 위 두 원소를 더해주는 것이 바로 결과값임을 알 수 있습니다. 제곱 역시도 최적화 하여 풉니다. 발상 자체는 굉장히 어렵지만, 문제 풀이 자체는 심플합니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Stair {
	
	public static int N = 0;
	public static long MOD = 1000000007;
	
	public static long matrix[][] = {{1, 1}, {1, 0}};

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		N = Integer.parseInt(br.readLine());
		
		
		long result = 0;
		if (N == 1) {
			result = 1;
		} else {
			long[][] ret = matrixPow(N - 1);
			result = (ret[0][0] + ret[0][1]) % MOD;
		}
		
		bw.write("" + result);
		bw.flush();
		bw.close();
	}
	
	public static long[][] matrixPow(int m) {
		
		if(m == 1) {
			return matrix;
		}
		
		long[][] half = matrixPow(m / 2);
		long[][] ret = matMultiply(half, half);
		
		if (m % 2 == 0) {	
			return ret;
		} else {
			long[][] ret2 = matMultiply(matrix, ret);			
			return ret2;
		}
	}
	
	public static long[][] matMultiply(long[][] A, long[][] B) {
		
		long[][] ret = new long[2][2];
		
		ret[0][0] = (A[0][0] * B[0][0] + A[0][1] * B[1][0]) % MOD;
		ret[0][1] = (A[0][0] * B[0][1] + A[0][1] * B[1][1]) % MOD;
		ret[1][0] = (A[1][0] * B[0][0] + A[1][1] * B[1][0]) % MOD;
		ret[1][1] = (A[1][0] * B[0][1] + A[1][1] * B[1][1]) % MOD;
		
		return ret;
	}
}