[백준 BOJ] 9465 스티커 (python)

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

9465번: 스티커

 

 

🔥 작성코드

T = int(input())
for _ in range(T):
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(2)]
    dp = [[arr[0][i], arr[1][i]] for i in range(n)]

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

    result = max(dp[n-1][0], dp[n-1][1])

    print(result)

 

 

⭕ 해설

1.  이전에 풀었던 rgb거리문제(https://dongkeun2.tistory.com/17?category=1018994)와 비슷한 방식으로 풀었습니다.
2.  일단 입력받은 2차원 배열을 2행 n열 => n행 2열로 바꾸어줍니다.
   • 기존 배열 : [[50, 10, 100, 20, 40][30, 50, 70, 10, 60]
   • 변경 배열 : [[50, 30], [10, 50], [100, 70], [20, 10], [40, 60]]
   • 제가 익숙한 배열로 풀기 위해 바꾼 것이고, 기존 배열을 쓰셔도 상관 없습니다.
3.  n=1 이라면 두 카드 중 큰 값을 뽑아내면 됩니다.
4.  n=2 이라면 대각선 카드의 합이 큰 카드 두 장을 뽑아내면 됩니다.
5.  n=3 이라면 경우의 수가 좀 더 많아집니다.
   • 지그재그로 3장을 뽑는 2가지 방법
   • 양 쪽 끝에서 왼쪽 위, 오른쪽 아래 or 오른쪽 위, 왼쪽 아래의 두 가지 방법
     • 한 장만 뽑는 경우 또는 양쪽 끝에서 왼쪽 위 or 오른쪽 위를 뽑는 경우는 무조건 위 경우보다 작음
   • 이 4가지 중 카드의 합이 가장 큰 카드들을 고르면 됩니다.
6.  여기까지 살펴보면 3번째 카드를 뽑을 때, 두 가지로 상황을 나눌 수 있습니다.
   • 위 카드를 뽑는 경우
     • 첫번째 위 카드 & 두번째 아래 카드
     • 첫번째 아래 카드
   • 아래 카드를 뽑는 경우
     • 첫번째 아래 카드 & 두번째 위 카드
     • 첫번째 위 카드
7.  dp를 활용하여 2번째 카드를 뽑는 순간(4번 상황)에 대각선의 합을 미리 2번 째 카드에 저장해놓으면
   •  3번째 위 카드를 뽑는 경우
     • 두번째 아래 카드 (첫번째 위 카드& 두번째 아래카드)
     • 첫번째 아래 카드
8.  따라서 4번째 카드를 뽑을 때에도 마찬가지로 반대방향의 3번째, 2번째 카드만 비교해주면 됩니다.
9.  0과 1에 값을 저장한 이후 2번부터 n-1번까지 진행한 이후 마지막 카드에 저장된 두 개의 값을 비교합니다. 

	0	1	=>		0	1
0	50	30		0	50	30
1	10	50		1	40	100
2	100	70		2	200	120
3	20	10		3	140	210
4	40	60		4	250	260

dp[4]에서 250과 260 중 큰 값인 260이 답이 됩니다.