아이디어

• 결정하고자 하는 우리의 행은 이전 행이
  • [비어있다]였으면 → [비어있다]/[왼쪽 칸에만 있다]/[오른쪽 칸에만 있다] 3개 중 하나다.
  • [비어있다]가 아니라면 → [비어있다]/[이전 칸과 다른 방향에 있다] 2개 중 하나다.
• n번 행이 [비어있다]일 경우의 수를 $a_n$, [비어있다]가 아닐 경우의 수를 $b_n$이라 하면
  ① $a_0 = 1$
  ② $b_0 = 2$
  ③ $a_{n+1} = a_n + b_n$ — 이전 경우가 [비어있다]일 때와 아닐 때 각각 1가지씩 경우가 생기므로
  ④ $b_{n+1}=2a_n + b_n$ — 마찬가지로 각각 2가지, 1가지의 경우가 생기므로
  이때 두번째 식을 $b_{n+1}=a_{n+1}+a_{n}$(⑤)으로 변형하면,
  $a_1$(←③), $b_1$(←⑤), $a_2$(←③), $b_2$(←⑤), … 등을 차례로 계산할 수 있다. $a_n+b_n$이 정답이 된다.
• 한편, 어떤 수들의 합의 모듈로를 구할 때는 더하는 값 자체 대신 그 값의 모듈로를 써도 된다.
  • $(x + y) \mod m = (x \mod m + y\mod m)\mod m$
  • 그러므로 overflow를 막기 위해 덧셈을 한 후마다 모듈로를 취해 범위를 줄여줘야 한다.

코드

import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    
    public static void main(String[] args) {
    	int n = sc.nextInt();

    	int tmp;
    	int a = 1;
    	int b = 2;
    	for (int i=0; i<n; i++) {
    		tmp = a;
    		a = (a + b) % 9901;
    		b = (tmp + a) % 9901;
    	}
    	
        System.out.println(a);
    }
}

메모리 및 시간

• 17656 KB / 208 ms

리뷰

• 배열 3개를 써서 구하는 법이 더 직관적이다.