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() 함수는 다음과 같은 역할을 수행한다.
- 입력 처리
- cin >> N;을 통해 정수 N을 입력받는다.
- DP 배열 초기화
- dp 벡터를 N+1 크기로 동적 할당한다.
- 각 dp[i]에는 크기 3의 벡터를 할당하여, dp[i][0], dp[i][1], dp[i][2] 값을 저장한다.
- 초기값 설정
- dp[1][0] = 1, dp[1][1] = 1, dp[1][2] = 1
- 이는 N=1일 때 가능한 경우의 수를 의미한다.
3. 동적 프로그래밍을 이용한 계산
이 프로그램은 점화식을 사용하여 dp[i] 값을 업데이트한다.
각 dp[i] 값은 다음과 같이 계산된다.
- 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
- dp[i][1]
- 현재 i번째 칸의 왼쪽에 동물이 배치된 경우, 이전 칸은 dp[i-1][0] (비어 있음) 또는 dp[i-1][2] (오른쪽에 배치됨)일 수 있다.
- 따라서, dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD
- 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();
}
'백준 > 동적프로그래밍' 카테고리의 다른 글
백준 12852 c++ "1로 만들기 2" -PlusUltraCode- (0) | 2025.02.17 |
---|---|
백준 1890 c++ "점프" -PlusUltraCode- (0) | 2025.02.17 |
백준 1965 c++ "상자넣기" -PlusUltraCode- (0) | 2025.02.10 |
백준 15988 c++ "1, 2, 3 더하기 3" -PlusUltraCode- (0) | 2025.02.10 |
백준 1699 c++ "제곱수의 합" -PlusUltraCode- (0) | 2025.02.10 |