백준 27114 (C++) 조교의 맹연습

최초 업로드: 2025-07-16 18:52:49

최근 수정 시간: 2025-07-25 08:45:03

게시자: rlatjwls3333

카테고리: 백준

# [Gold IV] 조교의 맹연습

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

## 문제 설명

공군 훈련소의 훈육조교는 훌륭한 조교가 되기 위해 오늘도 피나는 제식 연습을 진행한다. 오늘 연습하려고 하는 제식은 총 세 가지로, 현재 바라보는 방향을 기준으로 각각 왼쪽으로 $90\,^\circ$ 회전하는 <code>좌로 돌아</code>, 오른쪽으로 $90\,^\circ$ 회전하는 <code>우로 돌아</code>, 뒤로 $180\,^\circ$ 회전하는 <code>뒤로 돌아</code>이다.

<code>좌로 돌아</code>, <code>우로 돌아</code>,<code> 뒤로 돌아</code>를 $1$회 수행하는 데에는 각각 $A, B, C$만큼의 에너지가 든다. 오늘 조교의 총 에너지는 $K$만큼 남아있으며, 최고의 훈련을 위해 모든 $K$만큼의 에너지를 전부 소진하려고 한다.

조교는 본인의 에너지를 모두 소모하여 연습을 끝냈을 때 처음 바라보던 방향과 완벽히 동일한 방향을 바라보고자 한다. 또한, 어지러움으로 인한 흐트러짐을 막기 위해 제식의 수행 횟수를 최소화하고자 한다.

조교가 정확히 $K$만큼의 에너지를 소모하며 처음 바라보고 있던 방향을 바라보며 연습을 끝내고자 할 때 제식 수행 횟수의 최솟값을 구하여라.

## 입력

첫 번째 줄에 각각 <code>좌로 돌아</code>, <code>우로 돌아</code>,<code> 뒤로 돌아</code>에 들어가는 에너지를 나타내는 세 정수 $A, B, C$와 사용하고자 하는 총 에너지양을 나타내는 정수 $K$가 공백으로 구분되어 주어진다. $(1\leq A,B,C,K\leq 1\,000\,000)$

## 출력

정확히 $K$만큼의 에너지를 소모하며 처음 바라보고 있던 방향을 바라보며 연습을 끝내고자 할 때 제식 수행 횟수의 최솟값을 출력한다.

만약 정확히 $K$만큼의 에너지를 소모하며 처음 바라보고 있던 방향을 보는 것이 불가능하다면, $-1$을 출력한다.

## 풀이
#### 돌의 종류가 3개인 중복 냅색 문제처럼 풀었다.

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

const int INF = 0x3f3f3f3f;
int dp[1'000'001][4];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int a, b, c, k; cin >> a >> b >> c >> k;

fill(&dp[0][0], &dp[1'000'000][4], INF);
    dp[k][0]=0;

for(int i=k;i>0;i--) {
 for(int j=0;j<4;j++) {
 if(i-a>=0) dp[i-a][(j+1)%4] = min(dp[i-a][(j+1)%4], dp[i][j]+1);
 if(i-b>=0) dp[i-b][(j+3)%4] = min(dp[i-b][(j+3)%4], dp[i][j]+1);
 if(i-c>=0) dp[i-c][(j+2)%4] = min(dp[i-c][(j+2)%4], dp[i][j]+1);
 }
 }
 cout << (dp[0][0] == INF ? -1 : dp[0][0]);
}
```