[파이썬/Python] 백준 14430번: 자원 캐기

숨·2024년 9월 14일

코테

알고리즘 문제 풀이

목록 보기

74/105

📌 문제 : 백준 14430번

📌 문제 탐색하기

N : 탐사할 영역의 세로길이 $(1 ≤ N ≤ 300)$
M : 탐사할 영역의 가로길이 $(1 ≤ M ≤ 300)$

자원 위치를 알려주는 탐사영역 정보를 이용해 수집할 수 있는 최대 광석의 개수를 구하는 문제이다.

문제 풀이

⭐️ WOOK의 자원 탐색 방법

왼쪽 위 (1, 1) → 오른쪽 아래 (N, M)까지 탐색

이동 방향 2가지 : 오른쪽 또는 아래쪽 1칸

위치한 곳에 자원이 있을 때 채취 가능

1 : 자원 ⭕️

0 : 빈 땅

위치를 옮기는 방법은 2가지가 있고 자원을 최대로 얻어야 한다.
현 위치에 올 때 2가지 방법 중 자원의 최대 개수를 가지는 경로로 오도록 하면 될 것이다.

DP를 활용해 현 위치에서의 자원 최대 개수를 비교하면서 매번 최대의 자원 개수를 갖도록 해 원하는 값을 얻을 수 있도록 한다.

🔨 DP 테이블 정의

탐사 영역과 동일한 크기로 테이블을 정의한다.

탐사 시작 위치인 (1, 1)은 테이블에서 dp[0][0]을 의미한다.

초기화를 위해 dp[0][0]에 탐사영역 정보의 첫번째 칸 값을 넣어준다.

초기화를 위해 이동 방향에 따라 값을 먼저 채워준다.

첫번째 칸에서 오른쪽으로 이동하는 경우 = 첫번째 행 초기화

첫번째 칸에서 아래쪽으로 이동하는 경우 = 첫번째 열 초기화

가능한 시간복잡도

첫번째 행, 열 채우기 → $O(N), O(M)$
dp 테이블 채우기 → $O(N * M)$

최종 시간복잡도
$O(N * M)$ 로 최악의 경우 $O(300^2)$ 이 되는데, 이는 2초 내에 연산이 가능하다.

알고리즘 선택

모든 이동 시 2가지 경우에 대해 최댓값을 찾도록 DP 이용하기

📌 코드 설계하기

필요한 입력 받기
dp 테이블 정의
dp 테이블 채우기
결과 출력

📌 시도 회차 수정 사항

1회차

    dp[i][0] = dp[i-1][0] + search_areas[i][0]
    ~~^^^

첫번째 열 채우는 코드에서 IndexError: list index out of range가 발생했다.
알고보니 dp 테이블 정의를 dp = [[0] * M for _ in range(M)]로 잘못했다.
dp = [[0] * M for _ in range(N)]로 수정해 해결했다.

2회차

    print(dp[N][M])
          ~~^^^

최종 결과를 출력하는 부분에서 IndexError: list index out of range가 발생했다.
dp테이블은 인덱스 0부터 시작하기 때문에 1을 빼주어야하는데 그 부분을 빠트려서 발생한 에러였다.

📌 정답 코드

import sys

input = sys.stdin.readline

# N, M 입력
N, M = map(int, input().split())

# 탐색 영역 정보 입력
search_areas = [list(map(int, input().split())) for _ in range(N)]

# dp 테이블 정의
dp = [[0] * M for _ in range(N)]

# 테이블 초기화
dp[0][0] = search_areas[0][0]

# 첫번째 열 채우기
for i in range(1, N):
    dp[i][0] = dp[i-1][0] + search_areas[i][0]

# 첫번째 행 채우기
for j in range(1, M):
    dp[0][j] = dp[0][j-1] + search_areas[0][j]

# 테이블 채우기
for i in range(1, N):
    for j in range(1, M):
        dp[i][j] = max(dp[i-1][j] + search_areas[i][j], dp[i][j-1] + search_areas[i][j])

# 결과 출력
print(dp[N-1][M-1])