[BAEKJOON]1309 동물원

문제 요약

• 알고리즘 분류: 동적계획법, dp
• 난이도: Silver1
• 문제내용:
  • 가로가 N, 세로가 2인 사자 우리가 있다. 각 사자들이 가로 세로 겹치지 않게 배치 할수 있는 경우의 수를 구해라.

• 사이트: https://www.acmicpc.net/problem/1309

1309번: 동물원

문제풀이

 이번 문제는 데이터 길이가 10만이라서 O(N)시간에 풀어야 한다. 그래서 이번 문제 유형은  동적 계획법이다. 동적계획법의 자세한 설명은 여기에 확인 해보면 된다. dp문제는 구현하는 능력보다 아이디어를 요구하기 때문에 점화식을 짜는 방법만 알면 쉽게 풀수 있다.

문제 접근 방법

 1일때의 경우의 수는 왼쪽, 오른쪽, 아무것도 없을때 3가지로 보면 된고 2일때 직접 경우의 수를 구하면 7가지가 나올것이다. 그러면 3번째 부터 밑에 그림으로 올수 있는 경우의 수를 보면 된다.

일단 크게 위 그림에는 8가지 경우있는데 8가지 경우를 생각할 필요는 없다. 3개만 생각 하면된다.

1. 전 칸에 오른쪽 배치 할 경우
2. 전 칸에 왼쪽에 배치 할 경우
3. 전 칸에 아무것도 배치 하지 않을 경우

이 3가지 경우를 아래처럼 식을 만들수 있다. 그럼 1, 2번의 전 칸의 각가 경우의 수를 표현 하면 dp[i - 1]이고 3번은 dp[i - 2]값을 가져 오면된다. 그럼 다시 정리하면 1, 2번은 가져올 값은 같기 때문에 전것의 경우의 수를 곱하기 2하고 i - 2번 째 것을 더하면 된다.  점화식을 세우면 아래와 같은 식이 나온다.

dp[i]  = dp[i - 1] * 2 + dp[i - 2]

 

Code

Python

N = int(input())

dp = [3, 7]
for i in range(2, N):
    dp.append((dp[i - 1] * 2 + dp[i - 2]) % 9901)

print(dp[N - 1])

Java

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());
		if(N == 1) {
			System.out.println(3);
			System.exit(0);
		}
		int[] dp = new int[N + 1];
		dp[1] = 3;
		dp[2] = 7;
		for(int i = 3; i <= N; i++) {
			dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901;			
		}
		System.out.println(dp[N]);
	}
	
}