백준 파이썬 9465 스티커

🚀접근하기

처음 입력받은 배열과 (50 10 100 20 40) 두번째 입력받은 배열 (30 50 70 10 60) 을 입력받아 이차원 배열을 만들어 주었고, 똑같은 배열이지만 다 0 으로 채운 dp 배열을 만들어 주었다.

dp 문제인 만큼 case를 나누어 주었다.

case 1) 두 배열 중 윗 배열인 경우 (50 10 100 20 40 중)

case 2) 두 배열 중 아랫 배열인 경우 (30 50 70 10 60 중)

 

case 1)인 경우엔 dp 배열에서 자신의 왼쪽에 있는 숫자와, dp배열에서 자신의 왼쪽 대각선 밑에 있는 숫자 + 원래의 이차원 배열에서 자신의 숫자 중 더 큰 값을 dp 배열에서의 자신의 숫자로 입력해주었고,

 

case 2)인 경우에 dp 배열에서 자신의 왼쪽에 있는 숫자와, dp배열에서 자신의 왼쪽 대각선 위에 있는 숫자 + 원래의 이차원 배열에서 자신의 숫자 중 더 큰 값을 dp 배열에서의 자신의 숫자로 입력해주었다.

🎉코드

import sys

T=int(sys.stdin.readline())

for i in range(T):
    n=int(sys.stdin.readline())
    s_list=[list(map(int, input().split())) for _ in range(2)]
    dp = [[0 for _ in range(n)] for _ in range(2)]

    dp[0][0] = s_list[0][0]
    dp[1][0] = s_list[1][0]

    for i in range(1,n):
        for j in range(2):
            if j == 0:
                dp[j][i] = max(dp[j][i-1], dp[j+1][i-1]+s_list[j][i])
            else:
                dp[j][i] = max(dp[j][i-1], dp[j-1][i-1]+s_list[j][i])

    print(max(dp[0][n-1], dp[1][n-1]))

 

위에서 설명한 것을 코드로 작성하면 

            if j == 0:
                dp[j][i] = max(dp[j][i-1], dp[j+1][i-1]+s_list[j][i])
            else:
                dp[j][i] = max(dp[j][i-1], dp[j-1][i-1]+s_list[j][i])

이렇게 된다.

 

예제에 따르면 dp 배열은

50  50  200 200 250

30 100 120 210 260

이렇게 될 것이다.

💪다짐

#새로운 dp 배열을 만들었다면 하나하나 다 채울 생각을 하자.

#일단 자신 혼자의 입장에서 생각해본다. (넓게 보지 말고 나 위주로 보자)