백준 1309 c++ "동물원" -PlusUltraCode-

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

 

[필자 사고]

동적프로그래밍 문제이다.

필자는 점화식을 다음과 같이 설계했다.

1층 2층 3층 ... N층을 구별하고  빈곳 , 왼쪽, 오른쪽을 구별하기위해

dp[N][3] 이 배열을 만들었다.

 

그리고 빈곳은 dp[N][0] 

왼쪽 dp[N][1]

오른쪽 dp[N][2] 으로 정했고

dp[i][0] += (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2])%MOD;

dp[i][1] += (dp[i - 1][0] + dp[i - 1][2])% MOD;
dp[i][2] += (dp[i - 1][0] + dp[i - 1][1])% MOD;

다음과 같은 점화식을 이용하여 문제를 해결했다.

이 문제를 통해 느낀점은 dp의 점화식을 세우는게 문제를 푸는 핵심이다.

dp의 점화식을 새우는 방식은 좀 넓은 사고를 가지고 해야 될거같ㄷ.ㅏ

필자는 2*N배열이라서 반드시 dp[N][2] 형태로 어케 해야 풀 수 있을지 고민했는데

 

dp[N][3]의 형태로 바꾸니 쉽게 문제에 접근할 수 있었다.

문제에서 주어진 배열에 집중하기 보다는 내가 원하는 값을 얻기 위해 dp배열을 설계하자.

[코드 해설]

2. 입력 처리 (Game_Start 함수)

Game_Start() 함수는 다음과 같은 역할을 수행한다.

1. 입력 처리
   • cin >> N;을 통해 정수 N을 입력받는다.
2. DP 배열 초기화
   • dp 벡터를 N+1 크기로 동적 할당한다.
   • 각 dp[i]에는 크기 3의 벡터를 할당하여, dp[i][0], dp[i][1], dp[i][2] 값을 저장한다.
3. 초기값 설정
   • dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1
   • 이는 N=1일 때 가능한 경우의 수를 의미한다.

---

3. 동적 프로그래밍을 이용한 계산

이 프로그램은 점화식을 사용하여 dp[i] 값을 업데이트한다.
각 dp[i] 값은 다음과 같이 계산된다.

1. dp[i][0]
   • 현재 i번째 칸이 빈 상태일 경우, 이전 칸이 dp[i-1][0], dp[i-1][1], dp[i-1][2] 중 어떤 경우든 가능하다.
   • 따라서, dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % MOD
2. dp[i][1]
   • 현재 i번째 칸의 왼쪽에 동물이 배치된 경우, 이전 칸은 dp[i-1][0] (비어 있음) 또는 dp[i-1][2] (오른쪽에 배치됨)일 수 있다.
   • 따라서, dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD
3. dp[i][2]
   • 현재 i번째 칸의 오른쪽에 동물이 배치된 경우, 이전 칸은 dp[i-1][0] (비어 있음) 또는 dp[i-1][1] (왼쪽에 배치됨)일 수 있다.
   • 따라서, dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % MOD

[소스 코드]

#include <iostream>
#include <vector>
#define MOD 9901
using namespace std;

vector<vector<long long>> dp;
int N;

void Game_Start() {
	cin >> N;

	dp.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		dp[i].resize(3);
	}

	dp[1][0] = 1;
	dp[1][1] = 1;
	dp[1][2] = 1;

	for (int i = 2; i <= N; i++) {
		dp[i][0] += (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2])%MOD;

		dp[i][1] += (dp[i - 1][0] + dp[i - 1][2])% MOD;
		dp[i][2] += (dp[i - 1][0] + dp[i - 1][1])% MOD;


	}

	cout << (dp[N][0] + dp[N][1] + dp[N][2]) % 9901;
}

int main(void) {
	Game_Start();
}