[Python/BOJ] 27114. 조교의 맹연습

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

27114번: 조교의 맹연습

문제

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

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

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

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

입력

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

출력

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

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

풀이

Code

import sys
input = sys.stdin.readline

a, b, c, k = map(int, input().split())
# 1. 2차원 dp 생성
dp = [[1000001] * (k+1) for _ in range(4)]
# 2. 초기값 설정
dp[0][0] = 0

# 3.
for j in range(k+1) :
    for cost, dir in [(a,1), (b, 3), (c, 2)] :
        # 3-1. 예외처리
        if j + cost > k : continue
        # 3-2.
        for i in range(4) :
            # 예외 처리
            if dp[i][j] == 1000001 : continue
            # 점화식에 따라 처리
            direction = (i+dir) % 4
            dp[direction][j+cost] = min(dp[i][j] + 1, dp[direction][j+cost])
# 4. 결과 출력
print(-1) if dp[0][k] == 1000001 else print(dp[0][k])