[파이썬]백준 9465 스티커

링크

백준 9465 스티커

코드짜는시간은 5분도 안걸렸고 생각하는 시간이 30분 넘게 걸린 문제

두줄로 스티커가 주어지므로 두개의 리스트로 이를 받는다
그리고 각각의 리스트의 누적합중 max값을 0번 인덱스 값으로 초기화한다

그후 1번 인덱스부터 두개의 리스트를 동시에 탐색하며 각각의 리스트에서 해당 자리까지 도달했을 때 얻을 수 있는 누적합을 계산해나간다.
(머리속으로 빈 리스트를 만들고 누적합을 주어진 스티커 판과 같은 모양으로 채워나간다고 생각하면 이해하기 쉽다)

1번 인덱스를 계산하게 되면 반드시 다른 리스트의 누적합의 최댓값과 1번 인덱스의 값을 더하게 된다.

2번 인덱스 이후부턴 자신과 다른 리스트에 있는 누적합에다가 더할 수 밖에 없다. 왜냐하면 같은 리스트의 누적합의 경우 이미 해당 요소의 바로 왼쪽을 포함하고 있어 조건에 위배되기 때문이다.

단, 이때 가장 가까운 거리(바로 왼쪽 대각선)의 다른 리스트가 누적합 중 최대값임을 보장할 수는 없기 때문에 각각의 리스트의 누적합들 중 최대값을 계산해놓고 해당 최대값에 계산해야하는 요소의 값을 더하고 그중 큰 값을 최대값으로 유지한다.

그 후 두 리스트의 최대값 중 큰 값을 출력한다.

정답 코드

import sys; input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))
    arr1_max = arr1[0]
    arr2_max = arr2[0]

    for i in range(1, n):
        tmp_arr1_max = max(arr1[i] + arr2_max, arr1_max)
        arr2_max = max(arr2[i] + arr1_max, arr2_max)
        arr1_max = tmp_arr1_max

    print(max(arr1_max, arr2_max))

알게된 것👨‍💻

• 생각을 길게 코드 작성은 짧게! 이 편이 느려보이지만 사실 훨씬 빠르다!