[BOJ/백준] 1309 동물원

● [문제번호 1309] 동물원

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

1309번: 동물원

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: 알듯 말듯 하게 고민하다가 구글링을 통해 힌트를 얻었다.

 

: 왼쪽, 오른쪽 자리에다가 추가로 사자를 배치 안하는 열을 고려하여 만들면 된다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ index까지 사자를 배치하는 총 경우의 수를 저장한다.

// dp[index][0] : index자리에 사자 배치X
// dp[index][1] : index자리에 사자 왼쪽 배치
// dp[index][2] : index자리에 사자 오른쪽 배치

 

2. 점화식 찾기

index에 사자를 안 둔다면 이전에 모든 경우의 수를 가져온다.

dp[index][0] = (dp[index - 1][0] + dp[index - 1][1] + dp[index - 1][2])

 

index에 사자를 둔다면 이전에 사자를 배치 안 한 경우와 반대쪽에 배치한 경우를 가져온다.

dp[index][1] = (dp[index - 1][0] + dp[index - 1][2])

dp[index][2] = (dp[index - 1][0] + dp[index - 1][1])

위 두 값은 항상 동일하다.

 

3. 초기값 설정하기

→ 첫 번재 줄에 사자를 어디에 배치할 지는 각각 1가지로 총 3가지이다.

dp[1][0] = 1

dp[1][1] = 1

dp[1][2] = 1

예제 입력1 풀이과정

 

 

● 주의 할 것

: 나머지 연산을 주의해야한다.

 

 

● 참고 할 것

: 풀이과정 힌트

https://yabmoons.tistory.com/137

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// dp[index][0] : index자리에 사자 배치X
// dp[index][1] : index자리에 사자 왼쪽 배치
// dp[index][2] : index자리에 사자 오른쪽 배치
int dp[100001][3];
int N;

void zoo()
{
    // 초기값 설정
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][2] = 1;
    
    // 점화식
    for(int index = 2; index <= N; index++)
    {
        dp[index][0] = (dp[index - 1][0] + dp[index - 1][1] + dp[index - 1][2]) % 9901;
        dp[index][1] = (dp[index - 1][0] + dp[index - 1][2]) % 9901;
        dp[index][2] = dp[index][1];
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    zoo();
    
    cout << (dp[N][0] + dp[N][1] + dp[N][2]) % 9901;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [401 - 다이나믹 프로그래밍 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225