[백준 11048] 이동하기- python (solved.ac - 실버 1)

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

11048번: 이동하기

풀이

문제를 보았을 때 알 수 있는 힌트

문제 자체는 어렵지 않은 문제였다. 하지만 어떻게 풀면 시간초과도 날수있으니 조금 생각하며 풀어봐야하는 문제였다.

먼저 왼쪽끝에서 오른쪽 끝으로 움직이면서 큰 값만을 이동 시키면 되는 문제이다.

이를 담을 DP를 만들어 주면 된다. 나는 이를 추가한다는 느낌이 들어 stack이라고 정의하고 넣으면서 진행했다.

결과적으로 오른쪽 아래에 도착하게되면 최대의 값이 나오게 된다.

근데 이렇게 풀면 문제들이 빡빡해서 그런지 딱 1초 걸리며 문제를 해결하게 되었다.

import sys
from collections import deque
input = sys.stdin.readline

n,m = list(map(int,input().split()))

graph = []
stack = [[0]*(m+1) for _ in range(n+1)]
for i in range(n):
    graph.append(list(map(int,input().split())))

queue = deque()



for i in range(1,n+1):
    for j in range(1,m+1):
        stack[i][j] = graph[i-1][j-1]+ max(stack[i-1][j],stack[i][j-1],stack[i-1][j-1])
print(stack[-1][-1])

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/python/baekjoon11048.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리