[백준 16568] 엔비스카의 영혼 (C++)

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

문제

---

한길이는 수습 마법사이며, 마법사의 영혼을 받기 위해 줄을 서있다. 한길이는 강력한 힘을 얻기 위해 인성을 버렸다. 그리고 최고로 강력한 엔비스카의 영혼을 받기 위해서 새치기를 하기로 결심했다.

한길이의 앞에 N명의 사람들이 줄 서있다. 1초가 지날 때마다 줄의 맨 앞 사람은 영혼을 받고 집에 간다. 그리고 1초마다 한길이는 다음과 같은 행동을 할 수 있다.

• 기다리기
• a명 앞으로 가기 (앞에 최소 a명 있을 때)
• b명 앞으로 가기 (앞에 최소 b명 있을 때)

단, 한길이는 새치기에는 도가 텄기때문에, 모든 행동을 0초만에 할 수 있다.

예를 들어 N = 5, a = 1, b = 2라고 하자. 5초동안 기다리기만 하면 줄의 맨 앞 사람이 나가기 때문에 줄의 맨 앞에 서있기까지 5초가 걸린다. 하지만 맨 앞 한 명이 집에 가고 한길이가 2명 앞으로 새치기, 그 다음 한 명이 집에 가고 1명 앞으로 새치기하면 2초만에 줄의 맨 앞에 서게 된다. 유의할 점은 1초에 맨 앞 한 명이 가고 2명 앞으로 새치기하고 맨 앞 한 명이 가면 1명이 남는다. 이 때 2명 앞으로 새치기는 불가능하다.

한길이가 줄의 맨 앞에 서있으려면 최소 몇 초가 걸리는가?

입력

---

첫째 줄에 N, a, b가 주어진다. (0 ≤ N ≤ 1,000,000, 0 ≤ a, b ≤ N)

 

출력

---

한길이가 맨 앞에 서는데 걸리는 최소 시간을 출력한다.

 

문제 풀이

---

dp 문제.

 

1초마다 기다리는 행동을 할 수 있으므로 앞에 선 사람이 i명 있다고 한다면 적어도 N - i초 시간이 필요하고, 정답의 최댓값은 N이 된다. 이제 a명 앞으로 가는 행동과 b명 앞으로 가는 행동을 포함하여 계산하여 앞에 선 사람이 i명 있다고 할 때의 최소 시간을 줄일 것이다. 1초가 지날 때마다 사람이 한 명씩 줄어드므로, 현재 i명 있다고 할 때, a명 앞으로 가는 행동을 끝냈을 때에는 i-1-a명이 된다. 마찬가지로 현재 i명 있다고 할 때 b명 앞으로 가는 행동을 끝냈을 때에는 i-1-b명이 된다.

 

이를 이용하여 앞에 사람이 N-1명일 때부터 앞에 사람이 0명일 때까지 for문을 이용해 구해주면 된다.

dp[N] = 0이다.

1초 기다리는 행동을 했다면 dp[i] = dp[i + 1] + 1이고, a명 앞으로 가는 행동과 b명 앞으로 가는 행동은 각각 dp[i + a + 1] + 1와 dp[i + b + 1] + 1이 된다. 이 셋 중 가장 작은 값을 배열에 저장해주면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	int N, A, B;
	cin >> N>>A>>B;
	int* arr = new int[N + 1];
	arr[N] = 0;
	for (int i = N-1; i >= 0; i--)
	{
		arr[i] = arr[i + 1] + 1;
		if (i + A + 1 <= N)
		{
			arr[i] = min(arr[i], arr[i + A + 1] + 1);
		}
		if (i + B + 1 <= N)
		{
			arr[i] = min(arr[i], arr[i + B + 1] + 1);
		}
	}
	cout << arr[0] << "\n";
	return 0;
}