백준 34005 (C++) 초보자로 살아남기

최초 업로드: 2025-10-04 08:41:33

최근 수정 시간: 2025-10-04 08:41:33

게시자: rlatjwls3333

카테고리: 백준

# [Gold II] 초보자로 살아남기

[문제 링크](https://www.acmicpc.net/problem/34005)

## 문제 설명

pichulia 는 메이플스토리2 에서 초보자로 레벨 87까지 찍은 유저이다. 초보자로 모든 던전의 보스를 잡는다는 목표를 세웠던 pichulia 였지만, 어느 순간부터는 보스를 잡지 못하게 되었다. 상위 레벨의 던전에는 보통 10분 안에 보스를 잡아야 하는 제약사항이 있는데, 초보자의 데미지 수치로는 절대 잡을 수 없는 보스가 존재할 수 있던 것이다. 게임의 이러한 구조적인 불합리함을 느낀 pichulia 는 이 상황을 고발하기로 했다.

초보자가 쓸 수 있는 공격 스킬은 아래와 같이 총 4가지이다.

<table class="table table-bordered table-center-50 td-center th-center">
	<thead>
		<tr>
			<th scope="col">스킬</th>
			<th scope="col">데미지</th>
			<th scope="col">SP</th>
			<th scope="col">후 딜레이(초)</th>
			<th scope="col">쿨타임 (초)</th>
		</tr>
	</thead>
	<tbody>
		<tr>
			<td>기본 공격</td>
			<td>100</td>
			<td>0</td>
			<td>1</td>
			<td>1</td>
		</tr>
		<tr>
			<td>해머링</td>
			<td>$A$</td>
			<td>-7</td>
			<td>1</td>
			<td>1</td>
		</tr>
		<tr>
			<td>스트라이크</td>
			<td>$B$</td>
			<td>10</td>
			<td>2</td>
			<td>3</td>
		</tr>
		<tr>
			<td>박치기</td>
			<td>$C$</td>
			<td>10</td>
			<td>2</td>
			<td>8</td>
		</tr>
	</tbody>
</table>

각 항목에 대한 설명은 다음과 같다.

<ul>
	<li>데미지: 스킬 시전 즉시 데미지 수치만큼 몬스터의 체력을 감소시킨다.</li>
	<li>SP: 해당 스킬을 쓰는 데 필요한 자원. 양수이면 소모를, 음수이면 회복한다. 현재 SP가 소모량 미만일 경우 스킬을 쓸 수 없다.</li>
	<li>후 딜레이: 스킬 시전 후 경직되는 시간. 이 시간 동안 어떤 스킬도 쓸 수 없다. 스킬을 사용한 시점부터 시간이 계산된다.</li>
	<li>쿨타임: 같은 스킬을 쓰기 위해 필요한 대기 시간. 이 시간 동안 같은 스킬을 다시 쓸 수 없다. 스킬을 사용한 시점부터 시간이 계산된다.</li>
</ul>

예를 들어, 기본 공격 과 해머링 은 후 딜레이와 쿨타임이 같으므로 1초마다 한 번씩 계속해서 사용할 수 있다. 스트라이크 를 쓰면 1초 뒤에는 아무런 작업을 하지 못하고, 2초가 지난 뒤부터 스트라이크 를 제외한 다른 스킬을 쓸 수 있다. 3초 뒤부터는 스트라이크 를 쓸 수 있다.

SP는 1초에 1씩 회복되며. 최대 100 을 넘어가지 않는다. 또한 SP가 회복된 뒤에 스킬이 시전된다. 초기 SP는 100 이며, 1초부터 스킬을 사용할 수 있다.

각 스킬의 데미지가 주어졌을 때, 초기 체력이 $P$ 인 몬스터의 체력을 0 이하로 만들어 쓰러트리기 위한 시간의 최솟값을 구해보자.

## 입력

첫 번째 줄에는 테스트 케이스의 개수 $T$ 가 입력으로 주어진다. ($1 \le T \le 5$)

이후 $T$ 줄에 걸쳐 네 개의 정수 $A$ $B$ $C$ $P$ 가 공백으로 구분되어 주어진다. ($50 \lt A \lt 100;$ $200 \lt B \lt 400;$ $400 \lt C \lt 800;$ $400 \lt P \lt 10^6$)

## 출력

테스트케이스마다 한 줄에 하나씩 $T$ 줄에 걸쳐 몬스터를 쓰러트리기 위한 시간의 최솟값을 출력한다. 만약 $600$초가 지나도 몬스터에게 $P$ 이상의 데미지를 주지 못하는 경우 <code>-1</code> 을 출력한다.

## 풀이
dp[603][101][2][7]을 {초, 마나, 스트라이크 스킬의 쿨타임, 박치기 스킬의 쿨타임}으로 두고 풀었습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int a, b, c, p;
int dp[603][101][2][7]; // dp[i][j][k][l] : i초 j마나 스트라이크기 k쿨타임, 박치기가 l쿨타임일 때의 최대 데미지

int solve() {
    memset(dp, 0, sizeof dp);

for(int i=1;i<=600;i++) {
 int curMax=0;
 for(int j=0;j<=100;j++) {
 for(int k=0;k<=1;k++) {
 for(int l=0;l<=6;l++) {
 dp[i+1][min(100, j+1)][0][max(0, l-1)] = max(dp[i+1][min(100, j+1)][0][max(0, l-1)], dp[i][j][k][l]+100);
 dp[i+1][min(100, j+8)][0][max(0, l-1)] = max(dp[i+1][min(100, j+8)][0][max(0, l-1)], dp[i][j][k][l]+a);
 curMax = max({curMax, dp[i][j][k][l]+100, dp[i][j][k][l]+a});
 if(j>=10) {
 if(k==0) {
 dp[i+2][j-8][1][max(0, l-2)] = max(dp[i+2][j-8][1][max(0, l-2)], dp[i][j][k][l]+b);
 curMax = max(curMax, dp[i][j][k][l]+b);
 }
 if(l==0) {
 dp[i+2][j-8][0][6] = max(dp[i+2][j-8][0][6], dp[i][j][k][l]+c);
 curMax = max(curMax, dp[i][j][k][l]+c);
 }
 }
 }
 }
 }
 if(curMax>=p) return i;
 }
 return -1;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 cin >> a >> b >> c >> p;
 cout << solve() << '\n';
 }
}
```