[실버2]백준 11048번(이동하기) - 코테공부 28일차(2025.02.19)

문제유형

그리디 알고리즘

풀이 방법 도출 과정

1. 준규의 이동 경로는 오른쪽, 아래, 대각선 오른쪽 아래로 제한되어 있으므로, 각 위치에서 도달할 수 있는 최대 사탕 개수를 저장하는 DP 테이블을 구상할 수 있다. 

2. 구체적으로 각 위치 (r, c)의 값은 이전에 도달할 수 있는 세 위치 (r + 1, c), (r, c + 1), (r + 1, c +1) 중 최대값에 현재 위치의 사탕 수를 더한 값으로 갱신된다.

3. DP 테이블을 구성할 때, 아직 방문하지 않은 위치의 값은 0으로 초기화한다. "단, 가장 먼저 숫자가 0인 숫자는 최소화해야한다."라는 표현은 초기 상태나 경로 선택 시 0의 영향을 최소화해야 한다는 의미로 해석할 수 있으며, 이 경우 DP 테이블 초기화 및 경계 처리에 주의한다.

4. 모든 경로를 고려하여 (N, M)에 도달할 때의 최대 사탕 개수를 구하면, 문제의 정답이 된다. 

시간 복잡도

for 문 2개에 그리디 프로그래밍이 있기 때문에 최종적으로 시간복잡도는 O(N * M)이다. 

코드 및 간단설명

다이나믹 프로그래밍을 사용하였다. 

# 입력 받기
N, M = map(int, input().split())

# dp 테이블: (N+1) x (M+1) 크기의 2차원 리스트 (1-indexed로 사용)
dp = [[0] * (M + 1) for _ in range(N + 1)]

# 각 방의 사탕 개수를 저장할 리스트 (N행, M열)
candy = [list(map(int, input().split())) for _ in range(N)]

# dp 점화식 적용
# dp[i][j] : (i, j)까지 도달했을 때 모을 수 있는 사탕의 최대 개수
# (i, j)에 있는 사탕은 candy[i-1][j-1]에 해당하므로, 
# dp[i][j] = candy[i-1][j-1] + max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
for i in range(1, N + 1):
    for j in range(1, M + 1):
        dp[i][j] = candy[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])

# (N, M)까지 도달했을 때 모을 수 있는 최대 사탕 개수 출력
print(dp[N][M])

다른 풀이

1) 또 다른 다이나믹 프로그래밍 사용

위와는 더 효율적인 방법으로 한 것이다. 

N, M = map(int, input().split())
dp = [0] * (M + 1)  # 한 행의 DP 값을 저장할 배열

for i in range(N):
    prev = 0  # 이전 행의 (j-1)번째 값, 즉 dp[i-1][j-1]를 저장할 변수
    row = list(map(int, input().split()))
    for j in range(1, M + 1):
        temp = dp[j]  # 현재 dp[j]는 이전 행의 j번째 값 (dp[i-1][j])
        # dp[j-1]은 이미 현재 행에서 업데이트된 값 (dp[i][j-1])
        # prev는 dp[i-1][j-1]
        dp[j] = row[j - 1] + max(dp[j], dp[j - 1], prev)
        prev = temp  # 다음 열에서는 이전 행의 dp[i-1][j-1]로 사용됨
print(dp[M])