[알고리즘] - 스티커 (BOJ 9465)

• 이번 문제는 BOJ 9465, 스티커입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

• 문제의 유형 자체가 점화식을 활용하여 풀 수 있는 형태라고 판단하여, DP(Dynamic Programming) 방식으로 풀어보려고 접근했습니다.

  ✅Dynamic Programming(동적 계획법) : 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방식으로, 간단한 문제를 풀어냄으로써 그로 이루어진 복잡한 문제를 풀이하는 알고리즘 접근 방식입니다.

• 문제의 조건에 맞게 An 항을 An-1, An-2.. 항을 이용하여 점화식을 구하려고 시도했습니다. 이 과정에서 문제의 ‘스티커’가 하나의 행으로 이루어진 것이 아니라 2개의 행으로 이루어져 있다는 사실을 고려하여 접근했습니다.
• 일반적인 DP의 접근 방식과 동일하게 계산 과정에서 앞선 항이 반복적으로 호출된다는 점을 활용하여 시간 복잡도를 낮추기 위해 각 항별로 해당 항을 사용했을 때 스티커로 만들 수 있는 최고점을 이차원 리스트에 저장해나갔습니다.

점화식

• 스티커의 행이 2개라는 점을 고려하여, 아래와 같은 점화식을 세웠습니다.

  An의 첫 번째 행 = MAX(An-1의 두 번째 행, An-2의 두 번째 행) + 스티커의 An의 첫 번째 행의 점수

  An의 두 번째 행 = MAX(An-1의 첫 번째 행, An-2의 첫 번째 행) + 스티커의 An의 두 번째 행의 점수

• 여기서의 An은 스티커의 An번째 항을 사용하고자 할 때의 스티커를 통해 모을 수 있는 최고점을 저장해둔 항입니다.

• 이 점화식은 서로 변을 공유하는 스티커를 동시에 사용할 수 없다는 점에서 기인합니다. 즉, An의 첫번째 항을 사용하기 위해선 An-1의 첫 번째 항을 사용할 수 없습니다. 이 때문에 An-1의 두 번째 항을 선택하거나, An-1열을 포기하고 An-2의 두 번째 항을 선택하여야 합니다. 둘 중 큰 값을 지닌 항을 선택합니다.

• 여기서, An-2열의 첫 번째 항을 선택의 대상으로 고려하지 않는 이유는, An-2의 첫 번째 항의 경우 이미 An-1의 두 번째 항을 계산하는 과정에서 더해진 상태이기 때문입니다. 즉, An-2열의 첫 번째 항은 An-1열의 두 번째 항보다 반드시 작을 수 밖에 없기 때문에, 굳이 선택의 대상으로 고려하지 않아도 됩니다.
• 이 점화식을 활용하여, 스티커의 An번째 항을 사용했을 때의 확보할 수 있는 스티커 점수의 최고점을 저장해 나갑니다.
• 그리고 최종적으로, n번째 열의 첫 번째 항과 두 번째 항 중, 더 큰 값을 선택하여 출력합니다.

구현

# BOJ 9465
import sys
input = sys.stdin.readline

# 테스트케이스 입력
test_num = int(input().rstrip())

answer = []
for _ in range(test_num):
    # 스티커의 열의 개수를 입력 받음
    n = int(input().rstrip())

    # 스티커의 점수 정보를 이차원 배열로 입력 받음
    arr = []
    for _ in range(2):
        row_data = list(map(int, input().rstrip().split()))
        arr.append(row_data)

    # n이 1일 때와 2일 때는 초기값 설정 없이 바로 정답 저장
    if n == 1:
        answer.append(max(arr[0][0], arr[1][0]))
        continue
    elif n == 2:
        answer.append(max(arr[0][0] + arr[1][1], arr[0][1] + arr[1][0]))
        continue

    # 점화식 사용을 위한 이차원 배열 초기화
    res = []
    for _ in range(2):
        row = [0] * n
        res.append(row)

    # 1, 2번째 위치 초기화
    res[0][0] = arr[0][0]
    res[1][0] = arr[1][0]
    res[0][1] = arr[0][1] + arr[1][0]
    res[1][1] = arr[0][0] + arr[1][1]

    # 점화식 구현
    for i in range(2, n):
        res[0][i] = max(res[1][i-1], res[1][i-2]) + arr[0][i]
        res[1][i] = max(res[0][i-1], res[0][i-2]) + arr[1][i]

    # 둘 중 더 큰 것을 선택
    answer.append(max(res[0][n-1], res[1][n-1]))

# 출력 형식에 맞게 정답 출력
for ele in answer:
    print(ele)

• 위의 점화식은 An항을 구하기 위해 An-1, An-2를 활용하기 때문에, 초기화 과정에서 A1, A2 항은 직접 계산하여 입력하는 과정이 필요합니다.
• 이를 위해 n이 1이거나 2일 경우에는 따로 처리하는 로직을 추가했습니다.

Lesson

점화식을 구하는 과정에서 An이 실제로 두 개의 항으로 이루어졌기 때문에, 이를 구하는 과정이 조금 까다롭게 느껴졌던 것 같습니다. 그래도 이러한 유형의 문제를 만날 때 어떤식으로 풀이를 수행해야 할지 공부할 수 있었던 좋은 계기가 되었습니다.