[백준] 28017 게임을 클리어하자 (python 파이썬)

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

28017번: 게임을 클리어하자

---

대회 초반에 삽집하다가 DP인걸 깨닫고 해결했다. pypy로 제출, 이후 python으로 다시 제출.

---

아이디어

1. 반복문

• 단순 반복문으로 작성했다 실패했다. 

2. DP

• n회차의 각 무기마다 올 수 있는 시간을 저장하면 된다.

• 위 이미지처럼 이전 행에 있는 값 중 최솟값을 다음 행에 더해가며 업데이트하면 된다.
• 최종적으로 마지막 행의 최솟값을 출력하면 된다.

---

전체 코드 - pypy로 제출

import sys

INF = int(1e9)
N, M = map(int, input().split())
arr = []

for _ in range(N):
    arr.append([int(x) for x in sys.stdin.readline().split()])

for i in range(N - 1):

    for j in range(M):

        temp = INF

        for k in range(M):
            if arr[i][k] <= temp and j != k:
                temp = arr[i][k]

        arr[i + 1][j] += temp

print(min(arr[N - 1]))

---

코드 설명

for i in range(N - 1):

    for j in range(M):

        temp = INF

        for k in range(M):
            if arr[i][k] <= temp and j != k:
                temp = arr[i][k]

        arr[i + 1][j] += temp

위 설명한 부분을 코드로 구현한 것이다.

for문에 3개라 python으로 제출 시 시간 초과가 발생해 pypy로 제출했다.

---

추가) 전체 코드 - python3로 제출

import sys

N, M = map(int, input().split())
arr = []

for _ in range(N):
    arr.append([int(x) for x in sys.stdin.readline().split()])

for i in range(N - 1):

    for j in range(M):

        temp = min(arr[i][:j] + arr[i][j + 1:])

        arr[i + 1][j] += temp

print(min(arr[N - 1]))

 

파이썬의 slicing 기능을 사용해 시간을 단축시킬 수 있다.

python3로 제출하니 통과했다.

 

그리고 arr에서 이전행의 정보는 필요 없으므로 이를 이용해 배열 크기도 줄일 수 있다.