[Python] 27114번 조교의 맹연습

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

27114번: 조교의 맹연습

---

 

24/02/26

 

 

간단한 DP문제로, 처음엔 BFS로 잘못 접근했던 문제이다.

 

DP테이블 정의와 점화식 유도는 빠르게 할 수 있었지만, 자잘한 실수가 있어서 아쉬웠다.

---

 

문제 접근 방식:

 

 

$K$만큼의 에너지를 소모하여 처음 바라보고 있던 방향으로 제식 연습을 끝마쳤을 때 제식 수행 횟수의 최솟값을 구하는문제이다.

 

처음에는 BFS로 접근하고, 과도한 루프 방지를 위해 일정 루프 횟수를 넘어가면 종료하고 $-1$을 출력하는 방향으로 갔다.

 

시간 초과 및 틀렸습니다를 받고 DP적 접근으로 가보기로 했다.

 

아마 틀린 이유는 다른 제식 연습을 할 때마다 서로 다른 에너지를 소모하는데, 이를 그냥 돌려서 화근이었던 것 같다.

 

BFS는 가중치가 전부 $1$일 때 만 가능한 방법이다. 이 경우 가중치가 서로 다르다고 해석을 하는 것이 옳은 것 같다.  

 

$DP[p][j]$를 $j$의 에너지를 소모하여 $p$의 위치를 바라보며 연습을 끝낼 때 수행 횟수의 최솟값이라고 정의했다.

 

바라보는 위치는 $0$도, $90$도, $180$도, $270$도, 총 $4$가지 방향이 존재하므로 각각을 $0, 1, 2, 3$이라는 위치로 정의했다.

 

이 경우 점화식은 다음과 같이 나온다.

 

$$DP[p][j] = \mathrm{min}(DP[(p+1)\%4][j-A], DP[(p-1)\%4][j-B], DP[(p+2)\%4][j-C]) + 1$$

 

현재 위치가 $p+1$이라면, 왼쪽으로 $90$도 돌아야 $p$의 위치가 나오므로 다음과 같이 점화식을 구현했다.

 

$4$로 나눈 이유는 위치가 $4$가지 존재하고 이는 시계 방향으로 커지기 때문이다.

 

물론 저 해당 인덱스에 값이 존재하지 않을 수 있다. 이는 값이 존재하지 않음을 $-1$로 표현하고, 그때의 경우를 예외처리 해줌으로써 해결했다.

 

여러 번 실수했는데, 처음에는 방향을 헷갈리고, 두 번째는 초기 항을 잘못 세웠다. 세 번째로는 출력 값을 잘못 설정했고, 마지막으로는 for문을 $p$와 $j$의 순서를 반대로 하여 돌렸다.

 

초기항은 $DP[0][0]$을 $0$으로 설정함으로써 해결하였다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 27114번 조교의 맹연습
# DP
'''
접근 방법:
DP[p][j] = j의 에너지를 소모하여 p의 위치를 바라보며 연습을 끝낼 때 수행횟수의 최솟값
DP[p][j] = min(DP[p+1][j-A], DP[p-1][j-B], DP[p+2][j-C]) + 1
'''
import sys
input = sys.stdin.readline

A, B, C, K = map(int, input().split())
DP = [[-1 for _ in range(K+1)] for _ in range(4)]
DP[0][0] = 0
for j in range(1, K+1):
    for p in range(4):
        L = []
        if j - A >= 0 and DP[(p-1)%4][j-A] != -1:
            L.append(DP[(p-1)%4][j-A])
        if j - B >= 0 and DP[(p+1)%4][j-B] != -1:
            L.append(DP[(p+1)%4][j-B])
        if j - C >= 0 and DP[(p+2)%4][j-C] != -1:
            L.append(DP[(p+2)%4][j-C])
        if L != []:
            DP[p][j] = min(L) + 1
print(DP[0][K])