[백준/python] 9465번: 스티커

문제

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

9465번: 스티커

---

문제 요약

2행 n열로 배치된 2n개의 스티커들은 각 점수들을 갖고 있다.

이 스티커들 중 점수의 합이 최대가 되면서 변을 공유하지 않은 스티커 집합을 구하고, 그 집합의 점수 합을 출력한다.

 

---

코드

import sys
input = __import__('sys').stdin.readline

T = int(input())

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

    # arr는 초기에는 입력 받은 베열

    for j in range(1, n):
        if j == 1:
            arr[0][j] += arr[1][j - 1]
            arr[1][j] += arr[0][j - 1]
        # 1열일 때 초기 값 설정

        else:
            arr[0][j] += max(arr[1][j - 1], arr[1][j - 2])
            arr[1][j] += max(arr[0][j - 1], arr[0][j - 2])
        # 이전 두 경우의 수 중 큰 수에 자신을 더한 값으로 업데이트

    # 반복문을 통해 1열부터 n - 1열까지 접근하면서 arr[i][j]에 현재 상태에서 점수 합의 최대 값을 저장

    #print(*arr)

    print(max(arr[0][n - 1], arr[1][n - 1]))
    # arr의 마지막 열에서 두 경우의 수 중 큰 값을 출력

---

코드 설명

1. 입력 받은 2행 n열의 스티커 점수를 저장한 배열 arr을 생성한다.

+ 초기에는 입력 받은 배열을 저장하지만, 반복문을 통해 arr[i][j]에는 현재 상태(0열부터 j열까지만 있다고 가정한 상태)에서 점수 합의 최대 값으로 업데이트된다. (Bottom - Up 접근)

+ 따라서 arr은 Dynamic Programming의 메모이제이션 테이블 역할을 한다.

 

2. 반복문을 통해 1열부터 n - 1열까지 접근한다.

+ 0열은 자기 자신의 점수가 최대값이므로 따로 구할 필요가 없다.

 

3. j가 1일때, 즉 1열에는 아직 j - 2열이 존재하지 않으므로 따로 초기 값을 설정해준다.

 

4. 그 외 경우에는 arr[0][j], arr[1][j]는 각각 1행, 0행의 이전 열 또는 전전 열의 값  중 큰 값에 자신을 더한 값이 최대 점수이므로 업데이트 해준다.

 

+ 그림을 그려서 이해해보면 좋다. 

(출처: 항공대 코알라 코딩테스트 스터디)

 

5. 마지막 열까지 arr값을 업데이트 했다면, 마지막 열의 두 수 (두 경우의 수) 중 큰 수를 출력한다.