[백준] 1309. 동물원

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

 

DP를 이용해서 경우의 수를 따져가며 푼 문제이다. 

 

문제에는 2*N배열의 칸들이 있고, 여기에 사자를 배치할 때 서로 변을 공유하지 않도록 배치하는 경우의 수를 구하는 문제이다. 

이때 처음 행의 오른쪽에 사자를 배치하였을 때 나올 수 있는 경우의 수와 처음 행의 왼쪽에 사자를 배치하였을 때 나올 수 있는 경우의 수에 차이가 있을까?

오른쪽에 배치하느냐, 왼쪽에 배치하느냐에 따라 그 다음에 배치 가능한 경우의 수는 다르지 않기 때문에 경우의 수 자체는 다르지 않다.

즉,

(처음 행에 사자를 배치하지 않았을 때 나올 수 있는 경우의 수) + 2*(오른쪽 혹은 왼쪽 칸에 사자를 배치하지 않았을 때 나올 수 있는 경우의 수) = (모든 경우의 수)

인 것이다.

 

각 경우들은 재귀함수로 구하며, 문제의 조건에 따라 9901로 나눈 나머지를 구하는 연산도 필요하다.

---

C

#include <stdio.h>
#include <string.h>

int d[100000][3];
int n;

int dp(int depth, int position){
    if(depth == n-1) return 1;

    if(d[depth][position] != 0) return d[depth][position];

    if(position == 0){
        d[depth][position] = (dp(depth+1, 0) + (dp(depth+1, 1)*2)) % 9901;
        return d[depth][position];
    }
    else if(position == 1){
        d[depth][position] = (dp(depth+1, 0) + dp(depth+1, 2)) % 9901;
        return d[depth][position];
    }
    else{
        d[depth][position] = (dp(depth+1, 0) + dp(depth+1, 1)) % 9901;
        return d[depth][position];
    }
}

int main() {
    scanf("%d", &n);
    int res = (dp(0, 0) + (2*dp(0, 1))) % 9901;
    printf("%d\n", res);
}

---

Python

import sys
sys.setrecursionlimit(10**6)

def dp(depth, position): # position: 0->없음, 1->왼쪽칸, 2->오른쪽칸
    global d

    if depth == n-1: return 1 # base check

    if d[depth][position] != -1: return d[depth][position] # 저장된 값 활용

    if position == 0:
        d[depth][position] = (dp(depth+1, 0) + dp(depth+1, 1) + dp(depth+1, 2)) % 9901
        return d[depth][position]
    elif position == 1:
        d[depth][position] = (dp(depth+1, 0) + dp(depth+1, 2)) % 9901
        return d[depth][position]
    else:
        d[depth][position] = (dp(depth+1, 0) + dp(depth+1, 1)) % 9901
        return d[depth][position]

n = int(input())
d = [[-1 for _ in range(3)] for _ in range(n)]
res = (dp(0, 0) + dp(0, 1) + dp(0, 2)) % 9901
print(res)