백준 14916 c++ "거스름돈" -PlusUltraCode-

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

 

 

[필자 사고]

 

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

여기서 집중해서 봐야 될 부분은 2와 5이다.

dp라는 것의 idx가 의미하는 것은 현재 문제에서 주어지는 최선의 값을 도출하는 값이다.

즉 모든 dp가 최선의 값을 도출해야 된다는 점이다.

 

즉 필자는 아래와 같은 점화식을 만들었다.

dp[i] = min(dp[i-2],dp[i-5])+1; 

 

나머지 부분은 예외처리를 하면 쉽게 풀 수있다.

[코드 해설]

1. 게임 시작 (Game_Start 함수)

Game_Start 함수는 게임을 시작하는 역할을 하며, 특정 규칙을 기반으로 dp 배열을 사용하여 최적의 해를 구하는 동적 계획법(DP) 알고리즘을 구현한다.

2. 입력 처리

사용자로부터 정수 N을 입력받으며, 이를 바탕으로 dp 벡터를 크기 N+1로 초기화한다. dp 배열은 초기 상태에서 -1로 채워지며, 이후 특정 값들을 미리 설정한다.

• dp[0] = -1, dp[1] = -1 → 0 또는 1은 만들 수 없는 경우
• dp[2] = 1 → 2는 1개의 동작으로 만들 수 있음
• dp[3] = -1 → 3은 만들 수 없음
• dp[4] = 2 → 4는 2개의 동작으로 만들 수 있음
• dp[5] = 1 → 5는 1개의 동작으로 만들 수 있음

3. 동적 계획법 (DP) 적용

dp 배열을 이용하여 N까지의 값을 순차적으로 계산한다.
각 i에 대해, i-2 또는 i-5에서 동작을 추가하여 i를 만들 수 있는 최소 횟수를 저장한다.

• dp[i-2]와 dp[i-5]가 모두 -1이면 dp[i]도 -1 (만들 수 없는 경우)
• 하나만 -1이면, 가능한 쪽의 값을 기반으로 +1을 더하여 dp[i]를 설정
• 둘 다 유효한 값이면, 더 작은 값에 +1을 더한 값을 저장하여 최소 동작 횟수를 보장

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

vector<int> dp;
int N;

void Game_Start() {
	cin >> N;
	dp.resize(N + 1, -1);
	dp[0] = -1;
	dp[1] = -1;
	dp[2] = 1;
	dp[3] = -1;
	dp[4] = 2;
	dp[5] = 1;
	

	for (int i = 6; i <= N; i++) {
		if (dp[i - 2] == -1&& dp[i-5]==-1) {
			dp[i] = -1;
			continue;
		}
		else if (dp[i - 2] == -1) {
			dp[i] = dp[i - 5] + 1;
		}
		else if (dp[i - 5] == -1) {
			dp[i] = dp[i - 2] + 1;
		}
		else {
			dp[i] = min(dp[i - 2], dp[i - 5]) + 1;
		}
	}
	cout << dp[N];
}

int main(void) {
	Game_Start();
}