1309번 : 동물원 [Java]

https://www.acmicpc.net/problem/1309

1309번: 동물원

 

해결방안

 

2차원 배열을 사용해서도 풀 수 있었고 1차원 배열을 사용해서도 풀 수 있었다.

 

2차원 배열을 사용할 경우, dp[n][i]에서

i가 0 => n번째 줄에 배치 X = n-1 배치 X+ n-1 왼쪽에 배치 + n-1 오른쪽에 배치
i가 1 => n번째 줄 왼쪽에 배치하는 경우 = n-1 배치 X + n-1 오른쪽에 배치
i가 2 => n번째 줄 오른쪽에 배치하는 경우 = n-1 배치 X + n-1 오른족에 배치

 

1차원 배열을 사용할 경우, dp[n]에서
n-1번째 줄에 사자가 있다면 : 오른쪽 or 왼쪽 => dp[i-1]*2
n-1번째 줄에 사자가 없다면 : n-2줄 상황이랑 같음 => dp[i-2]

 

주의할 점

 

배치하는 경우의 수를 9901로 나눈 나머지를 출력해야 한다는 걸 까먹지 말자

1차원 배열일 때는 dp배열을 채우면서 나머지를 계산했고 그걸 바로 출력하기 때문에 출력 시 문제가 없지만,

2차원 배열일 때는 출력시 더해주는 과정이 생기기 때문에 한번 더 나머지 연산을 해주어야 한다.

 

 

전체 코드 1_ 2차원 배열

import java.util.Scanner;

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

		int[][] dp = new int[N + 1][3];

		dp[1][0] = 1;
		dp[1][1] = 1;
		dp[1][2] = 1;

		for (int n = 2; n <= N; n++) {
			dp[n][0] = (dp[n - 1][0] + dp[n - 1][1] + dp[n - 1][2]) % 9901;
			dp[n][1] = (dp[n - 1][0] + dp[n - 1][2]) % 9901;
			dp[n][2] = (dp[n - 1][0] + dp[n - 1][1]) % 9901;
		}
        
		System.out.println((dp[N][0] + dp[N][1] + dp[N][2]) % 9901);
	}
}

 

전체 코드 2_ 1차원 배열

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] dp = new int[N + 1];
		dp[0] = 1;
		dp[1] = 3;
        
		for (int i = 2; i <= N; i++) {
			dp[i] = (2 * dp[i - 1] + dp[i - 2]) % 9901;
		}

		System.out.println(dp[N]);
	}
}