글 읽기 - 100%틀렸습니다 반례구합니다

jmw93 3년 전 0

pypy3로 돌렸어요

구현은 , 동시에 최대/최소를 구하지않고 그냥 두번 반복돌아서 구했습니다.

100% 틀렸습니다 반례를 구합니다!!

N = int(input())
arr = [list(map(int,input().split())) for _ in range(N)]
dp =[[0,0,0],[0,0,0]]


dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]

#최댓값 구하기
for i in range(1,N): 
    dp[1][0] = max(dp[0][0],dp[0][1])+arr[i][0]
    dp[1][1] = max(dp[0][2],max(dp[0][0],dp[0][1]))+arr[i][1]
    dp[1][2] = max(dp[0][1],dp[0][2])+arr[i][2]
    
    dp[0][0] = dp[1][0]
    dp[0][1] = dp[1][1]
    dp[0][2] = dp[1][2]

ans_max = max(dp[0])

#최솟값 구하기 
dp[0][0] = arr[0][0]
dp[0][1] = arr[0][1]
dp[0][2] = arr[0][2]

for i in range(1,N):
    dp[1][0] = min(dp[0][0],dp[0][1])+arr[i][0]
    dp[1][1] = min(dp[0][2],min(dp[0][0],dp[0][1]))+arr[i][1]
    dp[1][2] = min(dp[0][1],dp[0][2])+arr[i][2]
    
    dp[0][0] = dp[1][0]
    dp[0][1] = dp[1][1]
    dp[0][2] = dp[1][2]

ans_min = min(dp[0])


print(ans_max,ans_min)
    