백준/14430번 :: 자원 캐기 (Python, 파이썬, 알고리즘)

 

문제

 

---

 

인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구해라!

 

입력

 

---

 

첫째 줄에 WOOK이 탐사할 영역의 세로길이 N(1≤N≤300)과 가로길이 M(1≤M≤300)이 주어진다. 그 다음 N행 M열에 걸쳐 탐사영역에 대한 정보가 주어진다. 숫자는 공백으로 구분된다. (자원은 1, 빈 땅은 0으로 표시된다)

 

출력

 

---

 

WOOK이 수집할 수 있는 최대 광석의 개수를 출력하라.

 

예제

 

---

 

예제입력

5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0

 

예제출력

4

 

코드

 

---

 

# -*- coding: utf-8 -*-
# Python 3.4.5
import sys
def go(x, y, dp, data) :
    if x < 0 or y < 0 :
        return 0 # 올바르지 않은 값
    if dp[x][y] != -1 :
        return dp[x][y] # 이미 연산된 값
    # 처음 연산하는 경우
    dp[x][y] = data[x][y]
    dp[x][y] += max(go(x-1, y, dp, data), go(x, y-1, dp, data))
    return dp[x][y]

# Main
if __name__ == '__main__':
    # 입력
    n, m = map(int, sys.stdin.readline().split())
    data = []
    for i in range(n) :
        temp = list(map(int, sys.stdin.readline().split()))
        data.append(temp)
    # 다이나믹
    dp =[[-1] * m for _ in range(n)]
    dp[0][0] = data[0][0]
    # 결과
    print(go(n-1,m-1, dp, data))​

 

다이나믹 프로그래밍을 이용했다.

 

특정한 (x, y)로 오는 방법은 (x-1, y)와 (x, y-1)밖에 없다. 위 2경우를 생각해서 풀어주면 된다.

 

결과

 

---

 

 

※ 직접 문제 풀고 돌려본 뒤, 채점까지 마친 후에 작성한 글입니다.

더 좋은 방법이 있다면, 댓글로 알려주시면 감사하겠습니다 :)

 

문제 출처

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