백준 2240 c++ "자두나무" -PlusUltraCode-

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

 

[필자 사고]

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

이 문제를 풀면서 확실히 동적프로그래밍에서 배열의 인덱스를 대하는 자세는 기존 배열 형태보다는

flag느낌으로 사용해야 된다는걸 다시 한번 느꼈다.

처음 배열에서는 time 두번째 배열은 pos 세번째 배열은 위치 이동 가능한 숫자 형태로 flag 형식으로 배열들을 선언하고
해당 조건들이 성공될 때 데이터를 업데이트 해주는 식으로 문제를 해결했다.

2차원에서 3차원으로 바꼇을 뿐인데 기존 고려할게 더 많아졌다.

 

아래는 자세한 소스코드 해설이다.

[코드 해설]

2. 입력 처리 (Input 함수)

Input() 함수는 게임의 기본 정보를 입력받아 초기화하는 역할을 한다.

• T, W를 입력받아 각각 총 시간과 이동 가능한 횟수를 저장한다.
• arr 벡터를 생성하여 각 시간마다 자두가 떨어지는 위치(1 또는 2)를 저장한다.
• dp 배열을 -1로 초기화하여, 아직 방문하지 않은 상태임을 나타낸다.

3. 동적 계획법을 이용한 게임 진행 (Game_Start 함수)

Game_Start() 함수는 DP를 활용하여 최대 점수를 계산하는 핵심 로직을 구현한다.

1. 초기 상태 설정: 시작 위치(1번 나무)에서 W번의 이동을 허용한 상태로 초기 점수를 0으로 설정한다.
2. DP 테이블 갱신:
   • 시간(time), 현재 위치(pos), 남은 이동 횟수(cnt)에 대해 3중 반복문을 수행한다.
   • 현재 상태에서 가능한 다음 상태를 확인하고, 점수를 갱신한다.
   • 같은 위치에 있는 경우 점수를 1 증가시키고, 다른 위치에 있다면 이동 가능할 경우 이동 후 점수를 증가시킨다.
3. 최대 점수 계산: 마지막 시간(T)에서 가능한 모든 경우 중 최대 점수를 출력한다.

4. 실행 흐름 (main 함수)

1. Input()을 호출하여 입력을 처리한다.
2. Game_Start()를 호출하여 DP 알고리즘을 수행하고 결과를 출력한다.

5. 핵심 개념

• DP 상태 정의: dp[time][pos][cnt]는 time 초일 때, pos 위치에서 cnt번 이동할 수 있는 상태에서 얻을 수 있는 최대 점수이다.
• 점화식:
  • 현재 위치에서 자두를 받을 경우 dp[time+1][pos][cnt] = max(dp[time+1][pos][cnt], dp[time][pos][cnt] + 1)
  • 위치를 변경할 경우 dp[time+1][nextPos][cnt-1] = max(dp[time+1][nextPos][cnt-1], dp[time][pos][cnt] + 1)

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

int dp[1001][3][31];
int T, W;
vector<int> arr;

void Input() {
	cin >> T >> W;
	arr.resize(T + 1);

	for (int i = 1; i <= T; i++) {
		cin >> arr[i];
	}

	memset(dp, -1, sizeof(dp));
}

void Game_Start() {
	dp[0][1][W] = 0;

	for (int time = 0; time < T; time++) {
		for (int cnt = 0; cnt <= W; cnt++) {
			for (int pos = 1; pos <= 2; pos++) {
				if (dp[time][pos][cnt] >= 0) {
					int nextPos = arr[time + 1];

					if (nextPos == pos) {
						dp[time + 1][pos][cnt] = max(dp[time + 1][pos][cnt], dp[time][pos][cnt]);
					}
					else {
						if (cnt > 0) {
							dp[time + 1][nextPos][cnt - 1] = max(dp[time + 1][nextPos][cnt - 1],
								dp[time][pos][cnt] + 1);
						}
						dp[time + 1][pos][cnt] = max(dp[time + 1][pos][cnt], dp[time][pos][cnt]);
					}
				}
			}
		}
	}

	int result = 0;
	for (int cnt = 0; cnt <= W; cnt++) {
		for (int pos = 1; pos <= 2; pos++) {
			result = max(result, dp[T][pos][cnt]); // 마지막 시간에서 최댓값 찾기
		}
	}
	cout << result << endl;
}

int main() {
	Input();
	Game_Start();
	return 0;
}