[baekjoon] 백준 9465번(파이썬): 스티커

문제

9465번: 스티커

알고리즘

- 반복문을 통해 각 스티커 인덱스의 최댓값을 구한다.

- 카드의 크기가 2일 때인 즉, 인덱스가 1일 때 최댓값은 이전 대각선의 스티커 점수의 합이다.

- 인덱스가 1보다 클 경우에는 두칸 전에 스티커 값과 이전 스티커 값 중에서 큰 값과 현재 스티커의 값을 더한 값이 최댓값이 된다.

- 표를 통해 확인하면 더 쉽게 이해할 수 있다.

예제 입력 1)

index	0	1	2	3	4
0	50	10 + 30 = 40	max(100, 30) + 100 = 200	max(120, 100) + 20 = 140	max(210, 120) + 40 = 250
1	30	50 + 50 = 100	max(40, 50) + 70 = 120	max(200, 40) + 10 = 210	max(140, 200) + 60 = 26

예제 입력 2)

index	0	1	2	3	4	5	6
0	10	30+ 20= 50	max(20, 50) + 10= 60	max(50, 80) + 50= 130	max(80, 110) + 100= 210	..	..
1	20	40+ 10= 50	max(10, 50) + 30= 80	max(50, 60) + 50= 110	max(60, 130) + 60 = 190	..	..

코드

import sys

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

# 테스트 케이스만큼 반복
for _ in range(t):
    n = int(sys.stdin.readline())
    m1 = list(map(int, sys.stdin.readline().split())) # 첫 번째 줄 스티커의 점수
    m2 = list(map(int, sys.stdin.readline().split())) # 두 번째 줄 스티커의 점수

    # 반복문을 통해 각 스티커 인덱스의 최댓값을 구한다.
    for i in range(1, n):
        # 인덱스가 1일때 최댓값은 이전 대각선의 스티커 점수이다.
        if i == 1:
            m1[1] += m2[0]
            m2[1] += m1[0]

        # 인덱스가 1보다 클 경우에는
        # 두칸 전에 스티커 값과 이전 스티커 값 중에서 큰 값과 현재 스티커의 값을 더한 값이 최댓값이 된다.
        else:
            m1[i] = max(m2[i - 1], m2[i - 2]) + m1[i]
            m2[i] = max(m1[i - 1], m1[i - 2]) + m2[i]

    print(max(m1[n - 1], m2[n - 1]))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법