BOJ/백준-11048-python

문제

풀이

• 그래프에 있는 사탕 개수의 최댓값을 가져와야 하는 문제다
• 모든 경우의 수를 체크해야하므로 다이나믹 프로그래밍 알고리즘으로 접근하였다.
• 1: (r+1, c) 2: (r, c+1) 3: (r+1, c+1) 이 세가지 방식 중에 제일 큰 수를 선택하도록 설정하면 된다.
• dp table을 초기화하여 그래프를 이동하여 얻는 사탕 개수를 계속 저장하였다.
• max함수로 3 가지 방식중 최댓값을 구한 뒤, 그래프의 이전값을 더하여 사탕을 모으는 과정을 구하였다.
• bottom-up 방식으로 구현하였다.

코드

# https://www.acmicpc.net/problem/11048
# boj, 11048: 이동하기, python3
import sys

input = sys.stdin.readline

def dp(n, m, graph):
    # dp table 초기화
    d = [[0 for _ in range(m+1)] for _ in range(n+1)]

    # dp bottom-up
    for x in range(1, n+1):
        for y in range(1, m+1):
            d[x][y] = max(d[x-1][y], d[x][y-1], d[x-1][y-1]) + graph[x-1][y-1]

    return d[-1][-1]

if __name__ == '__main__':
    n, m = map(int, input().split())
    graph = [list(map(int, input().split())) for _ in range(n)]

    print(dp(n, m, graph))

결과

출처 & 깃허브

BOJ 11048
github