[BOJ]11048(python)
BOJ - 11048(이동하기) python 풀이
DP를 이용해 풀이
보통 이런 문제는 dfs나 bfs로 풀이하는 것이여서
고민을 했는데
이 문구 덕분에 DP 를 이용해 풀이할 수 있었다
뒤로 돌아가는 등의 경우를 고려하지 않아도 되기 때문이다
코드
from collections import defaultdict
def solution():
N, M = map(int, input().split())
P = []
for _ in range(N):
P.append(list(map(int, input().split())))
count = defaultdict(lambda : defaultdict(int))
direction = [[0, -1], [-1, 0], [-1, -1]]
for y in range(N):
for x in range(M):
for d in direction:
by, bx = d[0] + y, d[1] + x
if count[y][x] < count[by][bx] + P[y][x]:
count[y][x] = count[by][bx] + P[y][x]
print(count[N-1][M-1])
solution()
- 배열을 순회하며 사탕의 갯수를 센다
- 현재 칸의 사탕 갯수 = 현재 칸에서 주어진 사탕 갯수 +
max(세로 축으로 한칸 전 사탕 갯수, 가로 축으로 한칸 전 사탕 갯수, 가로/세로 한칸 전의 사탕 갯수) - 마지막 칸의 사탕 갯수를 출력
Author And Source
이 문제에 관하여([BOJ]11048(python)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@zzarbttoo/BOJ11048python저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)