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

🥚문제

---

🥚입력/출력

---

🍳코드

코드 1

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
candy = [list(map(int, input().split())) for _ in range(n)]

# dp[r][c] = (r, c)로 이동할 때 가져올 수 있는 사탕 개수의 최대값
dp = [[0]*m for _ in range(n)]

# 움직일 수 있는 곳들
move_r = [1, 0, 1]
move_c = [0, 1, 1]

for r in range(n):
    for c in range(m):
        if dp[r][c] == 0:
            dp[r][c] = candy[0][0]
        for i in range(3):
            new_r = r + move_r[i]
            new_c = c + move_c[i]
            if 0 <= new_r < n and 0 <= new_c < m:
                dp[new_r][new_c] = max(
                    dp[new_r][new_c], dp[r][c] + candy[new_r][new_c])

print(dp[n-1][m-1])

코드 2 (개선)

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
candy = [[0]*(m+2)] + [[0] + list(map(int, input().split())) + [0] for _ in range(n)] + [[0]*(m+2)]

dp = [[0]*(m+2)] + [[0]*(m+2) for _ in range(n)] + [[0]*(m+2)]
for r in range(1, n+1):
    for c in range(1, m+1):
        dp[r][c] = max(dp[r][c], dp[r-1][c] + candy[r][c], dp[r]
                       [c-1] + candy[r][c], dp[r-1][c-1] + candy[r][c])
print(dp[n][m])

---

🧂아이디어

DP

• dp[r][c] = (r, c)로 이동할 때 가져올 수 있는 사탕 개수의 최대 값

• 코드 1
  • 입력이 아래와 같을 때
  • 각 공간에 있는 사탕의 개수를 저장하는 candy 및 dp를 (n)행 * (m)행짜리 2차원 리스트로 표현했다. (0, 0)부터 탐색
  • 따라서 index 범위를 벗어나지 않게 해 줄 필요가 있었기에 이중 반복문 내에 또 3가지 패턴의 움직임이 가능한지 검사해주는 과정이 필요하기 때문에 코드 실행 시간이 조금 더 길었다.

• 코드 2 (개선)
  • 입력이 아래와 같을 때
  • 각 공간에 있는 사탕의 개수를 저장하는 candy 및 dp를 (n+2)행 * (m+2)행짜리 2차원 리스트로 표현했다. 1 <= r < n+1, 1 <= c < m+1를 벗어나는 범위들은 0으로 표시했다. 움직인 뒤의 인덱스들이 범위를 벗어나는지 검사할 필요가 없어졌다.
  • 이중 반복문 내에서 dp[r][c] = max(dp[r][c], dp[r-1][c] + candy[r][c], dp[r][c-1] + candy[r][c], dp[r-1][c-1] + candy[r][c]) 코드만 실행해 주면 되기에 좀 더 시간을 단축할 수 있었다.