https://www.acmicpc.net/problem/1309
문제
> 어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.
> 이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다.
> 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.
> 동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자.
> 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.
접근
N이 주어졌을 때, 2xN짜리 크기의 사육장 안에 가로세로, 즉 상하좌우 칸에 아무것도 없어야한다.
N이 만약 4면 2x4짜리 사육장에 사자를 0마리, 1마리, 2마리, 3마리, 4마리 배치할 경우의 수의 총 합이 2x4의 결과값이다.
따라서 N이 1일때 부터 경우의 수가 적기 때문에 직접 따져본다.
1이면 0마리 - 1, 1마리 - 2가지 해서 총 3가지,
2면 0마리 - 1, 1마리 - 4, 2마리 - 2해서 총 7가지,
3면 0마리 - 1, 1마리 - 6, 2마리 -8, 3마리 - 2해서 총 17가지이다.
문제의 예제에서 4일 때, 41가지로 줬기 때문에
3, 7, 17, 41로 규칙을 구해보면, i번째일때의 경우의 수는 i-1의 2배 + i-2가 된다.
문제해결
> N을 입력받고 수가 커지기 때문에 long 타입으로 N을 위한 N-1까지의 경우의 수를 저장할 dp배열을 선언한다.
> N이 1부터 N까지이므로 크기를 N+1로 주어 1-based로 만들어준다.
> 사자를 넣지 않는 경우를 위해 초기값으로 1을 준다.
> 2x1크기의 사육장에 경우의 수로 dp[1] = 3을 준다.
> 이를 기반으로 2부터 N까지 반복문을 돌면 앞서 구한 공식으로 구한다.
> dp[i-1] * 2 + dp[i-2]로 i번 째의 경우의 수를 구해주고 문제 조건에 따라 99901로 나머지 연산해준다.
> 원하는 dp[N]값을 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//1309 동물원
static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
long[] dp = new long[N+1];
Arrays.fill(dp, 1);
dp[1] = 3;
for(int i = 2; i <= N; i++) dp[i] = (dp[i-1] * 2 + dp[i-2]) % 9901;
System.out.println(dp[N]);
}
}
후기
2xN 크기의 사육장에 최대로 넣을 수 있는 사자의 수를 구하는 문제인줄 알았는데
사지의 마릿수를 구하는게 아니라 해당 크기의 사육장에 사자를 키우는 경우가 몇가지냐는거였다.
