코딩 챌린지 6일차 : 14430번 자원 캐기(S2)

14430 : 자원 캐기 - 문제 링크

1. 문제 탐색하기

입력

n, m 세로, 가로의 길이
ground[n][m] 탐사영역에 대한 정보

구하고자 하는 것

탐색 가능한 자원의 최대 숫자
정해진 수의 이동 동안 최대의 자원을 채취해야 함

알고리즘 설계

로봇이 갈 수 있는 길은 오른쪽 또는 아래쪽으로 정해져있으므로
하나의 지점에 대해 두 가지 경우의 수만 고려하면 된다.

예제 입력 1을 참고
(5, 4)까지 최대 자원을 가지고 도달하기 위해서는
(5, 3)를 거치는 경로와 (4, 4)를 거치는 경로 두 가지(A[6]) 중
더 큰 자원을 가진 경로를 택해야 한다.

A[6] 중 더 큰 값을 가리기 위해서는 A[5]의 자원 수를 알아야 하고,
A[5] 중 더 큰 값을 가리기 위해서는 A[4]의 자원 수를 알아야 하고,
...
-> DP로 해결

따라 내려가다 보면
A[1]은 A[0]에 해당 위치의 자원 수를 더한 값이 된다. (2, 1)은 0, (1, 2)는 0+1=1
A[n]에서는 A[n]까지 올 수 있는 A[n-1] 두 가지 중 더 큰 값 (또는 유일한 값)을 택하여 A[n]의 자원 여부를 더한다.

입력받은 배열의 값을 변경하며 가질 수 있는 최대 자원 수를 기억한다.

점화식은 딱히 세울 수 없다고 판단되어 상단의 굵은 글씨와 그림으로 대체

시간복잡도

전체 그래프에 대해 탐색하므로 $O(mn)$
1 $\leq$ n, m $\leq$ 300이므로 최대 90,000번의 연산 수행 -> 통과 가능

2. 코드 설계하기

1. input 받기
2. 맨 윗줄은 무조건 왼쪽의 값만을 참조하므로 먼저 처리해준다. (시간 단축)
3. 점점 내려가며, 오른쪽으로 가며 자원의 가능 최댓값을 배열의 값으로 수정한다.
• 이 과정에서 맨 왼쪽 줄에 대한 처리도 해준다. (시간 단축)

3. 시도 회차 수정 사항

1회차) 후... 성공

4. 정답 코드

import sys
input = sys.stdin.readline

# input 받기
n, m = map(int, input().split())
ground = [list(map(int, input().split())) for _ in range(n)]

# 맨 위쪽은 왼쪽 값 합산
for j in range(1, m):
    ground[0][j] += ground[0][j - 1]

for i in range(1, n):
    # 맨 왼쪽은 위쪽 값 합산
    ground[i][0] += ground[i - 1][0] 
    for j in range(1, m):
        # 그 외는 왼쪽, 위쪽 중 큰 값 합산
        ground[i][j] += max(ground[i - 1][j], ground[i][j - 1])

print(ground[n - 1][m - 1])

처음에는 이게 어떻게 DP문제일까 싶었다. 사실 지금도 DP의 정의를 정확히는 알지 못해서 이 풀이가 DP인지 브루트포스인지 헷갈리긴 하는데... 실버2 문제인데 시간 소요를 너무 많이 해서 속상하다ㅠㅠ 그리고 글로 설명하기도 어려운 문제라 템플릿도 엉망진창으로 쓰기...

5. 해설지 참고 후

• 자정 이후 작성