dp2 동물원

[rhs0266]

dp2 동물원

[java-saeng]

손으로 하나씩 다 써보니까 제가 했던 방법은 말씀하신대로 사자가 아예 없을 경우는 뺀 경우의 수를 구하게 되네요

저는 마지막 +1 해주는 것이 사자가 없을 경우를 생각해서 더해준 것인데, 이 말은 즉, 전체에 사자가 없을 경우이지, 행마다 사자가 없는 경우를 더해준 적이 없는 것 같습니다. 그래서 +1한게 우연이 맞은 것 같네요,,

구글링과 다른 풀이법을 생각한 줄 알고 계속 붙잡고 있었는데 아니었군요,,, 도대체 dp는 감이 안잡히네요!!!!
읽어주셔서 감사합니다!! 해결됐어용 ㅎㅎ

ps. 혹시 선생님 강의 하시는 것이나 질문에 답해주신 풀이들 정리해서 블로그에 올려도 되나요,,, 출처는 깃헙주소로 밝히겠습니다. 예를 들어, 그래프 단원을 듣고 인접행렬, 인접리스트가 있고, 거기에 시간복잡도와 장단점, bfs는 언제 사용하는 지 등 pdf 그대로가 아닌 제 말로 해석해서 쓰고싶은데 혹시 가능할까요??

[her0807]

@java-saeng

안녕하세요. 저도 동물원 알고리즘으로 오늘 2시간 정도를 소요했는데요,

제가 비교적 간단한 점화식을 찾아내서 댓글 남깁니다.
기존에 강사님께서 도출하셨던 간단한 방법인데요,

n =1 일 때는 사자가 없거나, 왼쪽에 있거나 오른쪽이 있거나 해서 n =1 경우의 수가 3 입니다.

n = 2 일 때는 n =2 경우의 수 7 입니다.

n = 3 일 때는 n =2 경우의 수 17 입니다.

그리고 문제에서 n =4 경우의 수 41 을 주었으니 이 4개의 상관 관계를 따져보면

n 이 3 일때 dp[n-2] + (dp[n+1]*2) 를 하게되면 3+ (7*2) = 17 이 됩니다.

이 식을 참고해서 푸니

    private static void pro() {
        dp[1] = 3 % 9901;
        if(N>2) {
            dp[2] = 7 % 9901;
        }
        for (int i = 3; i <= N; i++) {
            dp[i] = (dp[i - 2] + (dp[i - 1] * 2)) % 9901;
        }
        System.out.println(dp[N] % 9901);
    }

이렇게 하면 풀리더군요. if 문을 걸어놓은 이유는, 만약 N = 1 일 경우에 오버플로우가 나서 방지하기 위함입니다!

제 코드도 참고해서 생각해주시면 감사하겠습니다 ㅎㅎ

그럼 즐거운 코딩 하세요 :)

[rhs0266]

dp[i][j] 의 정의가 어떻게 되시나요?

[java-saeng]

i 번째 줄 , j칸에 사자가 들어갈 수 있는 경우의 수입니다.

[java-saeng]

계속 생각해봤는데 제가 말씀드린 dp 정의가 말이 이상한 것 같습니다,,
규칙이 눈에 보였는데 문제가 풀리지 않아서 계속 붙잡고 있었던 것 같기도 합니다,,
값을 구할 때, i = N일 때, 답이 나와야하는데 애초에 잘못 생각했던 것 같습니다,,

[rhs0266]

말씀하신 방법으로 하면 적어주신 방법이 정답이 맞습니다. 올바르게 생각하신 거 맞아요!

다만 말씀하신 것처럼 i 가 커질수록 더해야 하는 게 많아지죠? 그 이유는 "i-1 번 줄에 사자가 한 마리도 없는 경우" 를 dp[i-1][0] 이나 dp[i-1][1] 로는 절대로 알 수 없기 때문입니다. 왜냐하면 dp[i-1][0]이나 [1] 모두 사자가 무조건 존재해야 하기 때문이죠.

저같은 경우는 j=2 인 경우를 새로 만들 것 같습니다.

dp[i][0] = 1번~i번 행에 사자를 올바르게 나열하는 방법들 중에서, i 번행 0 번 열에 사자가 있는 경우
dp[i][1] = 1번~i번 행에 사자를 올바르게 나열하는 방법들 중에서, i 번행 1 번 열에 사자가 있는 경우
dp[i][2] = 1번~i번 행에 사자를 올바르게 나열하는 방법들 중에서, i 번행에 사자가 전혀 없는 경우

이렇게 만들면 아마 고민하셨던 "식이 너무 길다" 가 해결되실 것 같아요.

[rhs0266]

넵 상관없습니다!

[java-saeng]

@her0807
이차원 배열 이용한 풀이는 직관적이어서 쉬운데
일차원 배열이 생각하기 어렵군요
코드 공유 감사드립니다.