[백준 9465] 스티커 - python (solved.ac - 실버 1)

https://www.acmicpc.net/problem/9465

9465번: 스티커

풀이

문제를 보았을때 알수있는 힌트

처음에 문제를 보고 단순하게 큰 값부터 계산하고 주변을 0으로 두면서 풀면 될까? 라는 생각을 가졌지만 여러 계산을 해보니 그렇게 풀면 발생하는 오류들이 많이 있어서 이것은 dp로 풀어야하는 문제라는 것을 파악하였다.

 

두개의 스티커를 1부터 차례대로 계산을 하면서 증가시키면 되는 문제였다.

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

위처럼 현위치에 있는 값을 더하고 이전에 있던 각각의 다른 위치의 값을 더하는 형식으로 계산한다.

이때 다른 위치의 그 이전의 값 중에서 큰 값을 비교해서 큰 값을 가져오며 비교하면 된다.

마지막으로 나온 값중 제일 큰 값을 출력하게 하면 끝이난다.

 

import sys

input = sys.stdin.readline

T = int(input())
for test_case in range(T):
    N = int(input())
    v1 = list(map(int,input().split()))
    v2 = list(map(int,input().split()))
    dp1=[0,v1[0]]
    dp2=[0,v2[0]]
    for i in range(0,N-1):
        dp1.append(max(dp2[i],dp2[i+1])+v1[i+1])
        dp2.append(max(dp1[i],dp1[i+1])+v2[i+1])
    print(max(dp1[-1],dp2[-1]))

 

https://github.com/dydwkd486/coding_test/blob/main/baekjoon/baekjoon9465.py

GitHub - dydwkd486/coding_test: 코딩테스트 공부한 내용 정리