[ BOJ ] 27114 : 조교의 맹연습 ( GOLD 4 ) / Python

문제

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

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

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

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

입력

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

출력

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

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

풀이 과정

초반에는 dp[i][j] : i 번째 방향을 바라보고 있으며 j 에너지를 사용했을 때 제식 수행 횟수의 최솟값 으로 생각했는데, 처음 바라보던 방향과 완벽히 동일한 방향을 바라봐야 하기에 더 고민해야 할 것이 있음을 깨달았다.

그러던 중 새로운 아이디어를 떠올렸는데, 처음 바라보던 방향과 완벽히 동일한 방향을 바라봐야 한다면 좌로 돌아, 우로 돌아, 뒤로 돌아 행위들을 새로운 행동 그룹으로 묶어 처음 바라보던 방향을 바라보는 제식 행위를 만들어 냅색으로 처리하면 되지 않을까 하는 생각이 들었다.

1. 좌로 돌아 - 좌로 돌아 - 뒤로 돌아
2. 우로 돌아 - 우로 돌아 - 뒤로 돌아
3. 좌로 돌아 - 우로 돌아
4. 뒤로 돌아 - 뒤로 돌아
5. 좌로 돌아 - 좌로 돌아 - 좌로 돌아 - 좌로 돌아
6. 우로 돌아 - 우로 돌아 - 우로 돌아 - 우로 돌아

다음과 같은 행동 그룹을 만들어 놓고, 사용하는 에너지를 합쳐 처음 방향으로 돌아오는 행동 그룹을 만들었다. 다른 행동이 섞인다고 한들 어차피 마지막에 처음 시작했던 방향으로 돌아와야 한다면 어떻게든 이 행동 그룹으로 나뉠 수 밖에 없다.

이렇게 풀이하니 수월하게 dp 를 구성할 수 있었다. dp[i] : i 에너지를 사용했을 때 제식 수행 횟수의 최솟값

import sys
input = sys.stdin.readline

a, b, c, k = map(int, input().rstrip().split())

dp = [float('inf') for _ in range(k+1)] 
dp[0] = 0

# 1. 좌로 돌아 - 좌로 돌아 - 뒤로 돌아
# 2. 우로 돌아 - 우로 돌아 - 뒤로 돌아
# 3. 좌로 돌아 - 우로 돌아
# 4. 뒤로 돌아 - 뒤로 돌아
# 5. 좌로 돌아 - 좌로 돌아 - 좌로 돌아 - 좌로 돌아
# 6. 우로 돌아 - 우로 돌아 - 우로 돌아 - 우로 돌아
arr = [(a+a+c, 3), (b+b+c, 3), (a+b, 2), (c+c, 2), (a+a+a+a, 4), (b+b+b+b, 4)]

for energy in range(1, k+1):
    for thing in range(6):
        if energy >= arr[thing][0]:
            dp[energy] = min(dp[energy], dp[energy - arr[thing][0]] + arr[thing][1])

print(dp[k] if dp[k] != float('inf') else -1)