[BaekJoon] 1309 동물원

1.  문제 링크

2.  문제

요약

• 가로로 두 칸, 세로로 N 칸의 우리가 있는 동물원에 사자들을 가두는데 가로로도 세로로도 붙어 있게 배치할 수 없을 때 2*N개의 배열에 사자를 배치하는 경우의 수를 구하는 문제입니다.
• 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 취급합니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 우리의 크기 N이 주어집니다.
• 출력: 첫 번째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;

public class Main {
	public long getArrangeNum(int num) {
		long[][] dp = new long[num + 1][3];
		dp[1][0] = dp[1][1] = dp[1][2] = 1;
		for(int i = 2; i <= num; i++) {
			dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
			dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
			dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
		}
		long arrangeNum = (dp[num][0] + dp[num][1] + dp[num][2]) % 9901;
		return arrangeNum;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getArrangeNum(num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 이 문제는 DP를 이용하여 점화식을 세워서 풀 수 있는 문제입니다.
• 2차원 배열 dp[N][L]에 대해서 N은 2칸짜리 우리 한 줄의 위치를 의미하고 L에 대해서 0은 해당 줄에 사자를 배치하지 않는 경우, 1은 해당 줄 왼쪽 칸에 사자를 배치하는 경우, 2는 해당 줄 오른쪽 칸에 사자를 배치하는 경우를 뜻합니다.
• 처음 dp[1][0], dp[1][1], dp[1][2]는 기저 사례로 모두 1로 설정합니다.
• dp[2][L]에 대해서
1. 두 번째 줄에 사자를 배치하지 않는 경우(dp[2][0])
• dp[2][0]인 경우에는 첫 번째 줄에 사자를 배치하는 경우의 수와 같기 때문에 dp[2][0] = dp[1][0] + dp[1][1] + dp[1][2] = 3이 됩니다.
2. 두 번째 줄의 왼쪽 칸에 사자를 배치하는 경우(dp[2][1])
• dp[2][1]인 경우에는 첫 번째 줄에 사자를 배치하지 않는 경우와 첫 번째 줄의 오른쪽 칸에 사자를 배치하는 수와 같기 때문에 dp[2][1] = dp[1][0] + dp[1][2] = 2가 됩니다.
3. 두 번째 줄의 오른쪽 칸에 사자를 배치하는 경우(dp[2][2])
• dp[2][2]인 경우에는 첫 번째 줄에 사자를 배치하지 않는 경우와 첫 번째 줄의 왼쪽 칸에 사자를 배치하는 수와 같기 때문에 dp[2][2] = dp[1][0] + dp[1][1] = 2가 됩니다.
• 위 예시를 통해 아래와 같은 점화식을 만들어낼 수 있습니다.
• dp[N][0] = dp[N - 1][0] + dp[N - 1][1] + dp[N - 1][2]
  dp[N][1] = dp[N - 1][0] + dp[N - 1][2]
  dp[N][2] = dp[N - 1][0] + dp[N - 1][1]
• 위에서 구한 점화식을 통해 N번째 줄에서의 사자를 배치하는 경우의 수를 구할 수 있습니다.

1. 주어진 N을 이용하여 long 타입의 2차원 배열인 dp[N + 1][3]을 생성하고 기저 사례인 dp[1][0], dp[1][1], dp[1][2]에 대해 1을 설정해줍니다.
2. 2부터 시작해서 주어진 N이 될 때까지 위에서 구한 점화식을 이용하여 현재 위치에서의 사자를 배치하지 않는 경우, 사자를 왼쪽 칸에 배치하는 경우, 사자를 오른쪽 칸에 배치하는 경우를 구하고 경우의 수를 9901로 나눈 나머지를 구하라고 하였으므로 각각 9901로 나눈 나머지를 해당 위치의 dp 배열에 설정합니다.
3. 주어진 N까지 돌았다면 dp[N][0] + dp[N][1] + dp[N][2]를 구하고 이를 9901로 나눈 나머지를 출력합니다.