[백준-파이썬] 9844: Gecko

문제 풀러 가기!

주어진 예제 1을 풀이하면 아래 그림처럼 된다. !

dp - 모든 위치를 보면서 그 위치일 때 가장 큰 값을 저장했다.
일단 h가 0일 때는 tiles 값 그대로가 그 위치일 때 가장 큰 값이다.
y좌표 1 이상이 될 때부터는..

1) x좌표가 0이거나 w-1이면, y좌표가 현재 지점보다 1 적을 때 바로 위, 한쪽 대각선 중에(그림의 파란색 화살표들 참고) 큰 값을 택한다. 그 값과 tiles 자기 위치 값(그림에서 초록색 값)을 더한다.
2) x좌표가 1~ w-2라면, y좌표가 현재 지점보다 1적을 때 바로 위, 좌측 대각선 위, 우측 대각선 위 중(그림의 노란색 화살표 참고) 큰 값을 택한다. 그 값과 tiles 자기 위치 값(그림에서 초록색 값)을 더한다.

y좌표가 h-1까지 오면, 그때 값들 중에(그림에서 빨간색 네모 친 부분) 최대값이 정답이 된다!

코드 🧡

import sys
input = sys.stdin.readline

MIISS = lambda: map(int, input().strip().split())

h, w = MIISS()
tiles = tuple(tuple(MIISS()) for _ in range(h))
dp = [[0]*w for _ in range(h)]

# 첫줄은 채우기
dp[0] = tiles[0]

# 만약에 w가 1이면
if w == 1:
    ans = 0
    for i in range(h):
        ans += tiles[i][0]
    print(ans)
else:
    # 최대 수
    for i in range(1, h):
        # 맨 앞
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + tiles[i][0]

        # 중간
        for j in range(1,w-1):
            dp[i][j] = max(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + tiles[i][j]

        # 맨 뒤
        dp[i][w-1] = max(dp[i-1][w-1], dp[i-1][w-2]) + tiles[i][w-1]

    print(max(dp[h-1]))

 

그리고..

나는 h가 2 이상이고, w가 1이면 에러가 나서..(아래 예시 입력처럼)

5 1
1
2
3
4
5

'만약에 w가 1이면' 부분을 작성했다.
그런데 저 부분이 없어도 맞았습니다!가 뜨기는 한다.