백준 1309(동물원)

jh Seo·2024년 6월 18일
0

백준

목록 보기
182/194
post-custom-banner

개요

백준 1309 동물원

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

접근 방식

  1. 세가지 경우로 나눌 수 있다.
    1. 우리 왼쪽에 사자가 배치되었을 때
    2. 오른쪽에 사자가 배치되었을 때
    3. 아무 쪽도 배치 안 되었을 때
  1. 따라서 이차원 배열을 선언했다.
    int dpArr[100'000][3]
    0일 때 {0,0}, 1일 때 {0,1}, 2일 때 {1,0} 이렇게 구분했다.
  1. TOP-DOWN 방식으로 접근 했는 데 ,
    각 단계에서 idx, idx2값을 통해 dpArr의 값을 호출했다.
    idx는 각 단계이고(1~ 100'000), idx2는 각 단계의 상태이다. (사자의 배치 상태)

    idx2가 0이면 현재 0,0을 넣어야 한다는 소리이므로 이전 idx값에서 idx2가 0,1,2 값을 모두 더해준다.

    idx2가 1이면 현재 0,1을 넣어야 한다는 소리이므로 이전 idx값에서 idx2가 0일 때와 2인 값만 더해준다.

    idx2가 2이면 현재 1,0을 넣어야하므로 이전 idx값의 idx2가 0일때와 1인 값만 더해준다

전체코드

#include<iostream>
#include<vector>

using namespace std;

//0 for 0,0 / 1 for 0,1 / 2 for 1,0
int dpArr2[100'002][3];
int N;

int Dp(int idx, int idx2) {
   int* ret = &dpArr2[idx][idx2];
    if (idx == 0) {
        *ret = 1;
        return *ret;
    }
    if (*ret != -1) return *ret;   

    if (idx2 == 0)
        *ret = ((Dp(idx - 1, 0) % 9901) + (Dp(idx - 1, 1) % 9901) + (Dp(idx - 1, 2) % 9901))%9901;
    else if (idx2 == 1)
        *ret = ((Dp(idx - 1, 0) % 9901) + (Dp(idx - 1, 2) % 9901))%9901;
    else
        *ret = ((Dp(idx - 1, 0) % 9901) + (Dp(idx - 1, 1) % 9901))%9901;

    return *ret % 9901;
}

int main() {
    cin >> N;
    fill(&dpArr2[0][0], &dpArr2[100'001][2], -1);
    int answer = (Dp(N-1, 0) + Dp(N-1, 1) + Dp(N-1, 2))%9901;
    cout << answer % 9901;
}

문풀후생

처음 풀이 때 틀린 부분이 두번 있었다.

처음 틀린 부분은

    fill(&dpArr2[0][0], &dpArr2[100'000][2], -1);

이렇게 초기화 해줘서 틀렸다.
fill의 두번째 값은 끝 경계여서 초기화가 안된다!
dpArr2[100'000][2]를 출력해보면 -1이 아니라 0이 나온다.

두 번째 틀린 부분은
0까지 depth를 내려가게 해놓고 호출을

    int answer = (Dp(N, 0) + Dp(N, 1) + Dp(N, 2))%9901;

이렇게 호출하여 한번 더 실행되어 값이 크게 나왔다.

위 처럼 answer을 구하려면

    if (idx == 1) {
        *ret = 1;
        return *ret;
    }

이렇게 구현하거나

0까지 내려가게 하고싶으면

int answer = (Dp(N-1, 0) + Dp(N-1, 1) + Dp(N-1, 2))%9901;

이렇게 변경해야한다!

profile
코딩 창고!
post-custom-banner

0개의 댓글