[Silver I] 동물원 - 1309
성능 요약
메모리: 15048 KB, 시간: 88 ms
분류
다이나믹 프로그래밍
제출 일자
2024년 1월 28일 16:10:15
문제 설명
어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.
이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.
동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.
입력
첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.
출력
첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.
접근 방법
1. DP로 풀면 좋겠다는 생각이 들었다.
2. 문제의 조건은 아무것도 놓지 않았을 때, 왼쪽, 오른쪽인 경우가 있다.
3. 처음에는 아무것도 놓지 않았을 때 경우, 왼쪽인 경우, 오른쪽인 경우들의 배열을 선언하여 더하였음
4. 그러다보니 왼쪽,오른쪽은 대칭이기 때문에 * 2를 한다면 점화식이 세워진다.
즉,
DP[i][0] (아무것도 놓지 않은 경우) = (DP[i-1][0] + DP[i-1][1] * 2) % MOD
DP[i][1] (왼쪽 혹은 오른쪽에 놓여진 경우) = (DP[i-1][0] + DP[i-1][1]) % MOD
로 계산이 가능하다.
import java.util.*;
import java.io.*;
public class Main {
static final int MOD = 9901;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
// 경우의 수 3가지 - 현재 위치에 사자를 안놓는 경우[0], 왼쪽에 놓는 경우[1], 오른쪽에 놓는 경우[2]
int[][] dp = new int[n + 1][3];
// N = 1일 때는 경우의 수가 모두 1이다.
dp[1][0] = 1;
dp[1][1] = 1;
// 2부터 N까지 진행
for (int i = 2; i <= n; i++) {
// 아무것도 놓지 않는 경우는 위에 모든 경우의 수(아무것도 없을 때, 왼쪽일 때, 오른쪽 일 때)를 더한 것.
dp[i][0] = (dp[i-1][0] + dp[i-1][1] * 2) % MOD;
// 왼쪽인 경우 - 이전 경우가 아무것도 없을 때, 오른쪽일 때
// 오른쪽인 경우 - 이전 경우가 아무것도 없을 때, 왼쪽일 때
// 즉 대칭이므로 아무것도 없을 때 + 왼쪽인 경우만 담음
dp[i][1] = (dp[i-1][0] + dp[i-1][1]) % MOD;
}
System.out.println((dp[n][0] + dp[n][1] * 2) % MOD);
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 14731번 : 謎紛芥索紀 (Large) Silver1(실버1) - JAVA[자바] (0) | 2024.06.18 |
---|---|
[백준] 14716번 : 현수막 Silver1(실버1) - JAVA[자바] (1) | 2024.01.29 |
[백준] 1326번 : 폴짝폴짝 Silver2(실버2) - JAVA[자바] (1) | 2024.01.24 |
[백준] 1389번 : 케빈 베이컨의 6단계 법칙 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |
[백준] 11403번 : 경로 찾기 Silver1(실버1) - JAVA[자바] (0) | 2024.01.16 |