[백준/28450번] 컨벤 데드가 하고싶어요 - S2/Python

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

문제

헬린이 재현이는 하체를 키우는 데에 있어 컨벤셔널 데드리프트(땅에서부터 바벨을 들어 올리는 운동)는 무조건 해야 한다고 믿는다. 그러나 컨벤셔널 데드리프트의 최대 단점은 바로 소음이다. 들어 올린 후 땅에 다시 내려놓을 때 받침대가 있더라도 소음과 진동이 발생하기 마련이다. 그리하여 아무리 컨벤 데드가 허락된 헬스장에서도 헬스장의 깐깐한 헬창 형님들은 수수깡같이 나약한 몸뚱아리를 가진 재현이가 감히 컨벤 데드를 하는 것을 용납하지 못한다. 재현이가 헬창 형님들 몰래 컨벤 데드를 하는 것을 도와주자.

헬스장 입구에서 컨벤셔널 데드리프트를 할 바벨이 있는 곳까지 가는 지도가$N \times M$ 크기의 격자 모양으로 주어진다. 헬스장 입구는 지도상 왼쪽 상단($1$행 $1$열)에 위치하며 바벨은 우측 하단($N$행 $M$열)에 위치한다. 각 칸에는 헬창 형님들이 존재할 수 있고 각각의 헬창 형님들은 눈치력을 갖고 있다. 재현이가 헬스장 입구에서 출발하여 바벨까지 가는 도중 마주치는 헬창 형님들의 눈치력의 총합이 재현이의 은신력보다 크다면 재현이는 컨벤 데드를 못 하게 된다. (마주친다는 건 헬창 형님과 재현이가 같은 칸에 위치했음을 뜻한다.) 이동 방향은 오른쪽 또는 아래쪽만 가능하다. 재현이는 지도 바깥으로 나갈 수 없다. 재현이의 은신력 $H$가 주어질 때 재현이가 컨벤 데드를 할 수 있는지 없는지를 구하라.

입력

첫 번째 줄에 $N$, $M$이 주어진다. ($1 \leq N, M \leq 1,000$)

두 번째 줄부터 $N$개의 줄에 걸쳐 $M$개의 수로 지도가 주어진다. 지도에서 $0$은 빈 공간을, 양의 정수는 그 칸에 있는 헬창 형님의 눈치력을 나타낸다.

마지막으로 재현이의 은신력 $H$가 주어진다.

재현이의 은신력과 헬창 형님들의 눈치력은 모두 $1$ 이상 $100,000,000$ 이하의 정수다.

풀이

n, m = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(n)]
hide = int(input())
dp = [field[x][:] for x in range(n)]
for i in range(1,m):
    dp[0][i] += dp[0][i-1]
for i in range(1,n):
    dp[i][0] += dp[i-1][0]
for i in range(1,n):
    for j in range(1,m):
        dp[i][j] += min(dp[i-1][j], dp[i][j-1])
if dp[-1][-1] <= hide:
    print('YES')
    print(dp[-1][-1])
else:
    print('NO')

해결방법

필드에 크기와 동일한 DP 배열을 선언한 다음에 첫번째 열과 첫번째 행의 누적값을 구한 다음에 나머지 영역에 대해서는 해당 위치의 왼쪽 및 위쪽 중 작은 값을 찾아서 갱신하면 되는 문제.
이후, 컨벤 데드 기구 위치의 눈치력이 재현이의 은신력보다 큰지 판단하여 조건에 맞게 출력하면 문제 해결 가능.