BOJ - 1309

BOJ - 1309

(문제 : https://www.acmicpc.net/problem/1309)

문제 해결 방법

1. 빈칸을 채워 넣는 단순한 DP 문제로 생각함.
2. 맨 아래 칸에 사자가 없는 경우, 왼쪽에 있는 경우, 오른쪽에 있는 경우를 나누어 계산.
3. 동물원에 사자가 없는 경우도 있으니 주의!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());

		int none = 1; // 맨 아래 사자가 없는 경우
		int left = 1; // 맨 아래 사자가 왼쪽에 있는 경우
		int right = 1; // 맨 아래 사자가 오른쪽에 있는 경우

		for(int i = 0; i < N - 1; i++) {
			int tmp_n = none;
			int tmp_l = left;
			int tmp_r = right;

			none = (tmp_n + tmp_l + tmp_r) % 9901;
			left = (tmp_n + tmp_r) % 9901;
			right = (tmp_n + tmp_l) % 9901;
		}

		System.out.println((none + left + right) % 9901);
	}

}

후기

단순한 DP 문제여서 크게 어려움은 없었다. 처음 생각할 때 맨 아래에 왼쪽에 있는 경우, 오른쪽에 있는 경우를 생각안하고 아래에 있는 경우로만 생각했지만 잘못 생각했는지 다른 답안이 나왔다..
다행히 바로 경우의 수를 나누어서 생각해서 빨리 풀었다.