백준 9465: 스티커

델리만쥬 디퓨저·2025년 11월 27일

알고리즘

목록 보기

20/25

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

입출력 분석

2차원 배열 값이 입력으로 주어지고, 변을 공유하지 않는 스티커 점수의 최대 값 출력
100,000개의 n이 입력되며, 1초 안에 수행되어야 하므로 O(N^2)는 불가

알고리즘 분석

이전의 선택을 바탕으로 최선의 결과를 선택해 쌓아올리는 방식인 DP가 적합

점화식 세우기

i번째 열에서 선택 가능한 경우의 수는 다음과 같다

위쪽 스티커 떼기

아래쪽 스티커 떼기

아무것도 안 떼기

score[i][0] = max(score[i-1][1], score[i-2][1]) + arr[i][0]
score[i][1] = max(score[i-1][0], score[i-2][0]) + arr[i][1]

i-2까지 고려하는 이유는, 아무것도 선택하지 않고 넘어간 다음 선택하는 경우가 최적일 수 있기 때문이다.

1차 풀이

import sys  
  
input = sys.stdin.readline  
  
t = int(input())  
for _ in range(t):  
    n = int(input())  
    arr = [list(map(int, input().split())) for _ in range(2)]  
    score = [[0] * n for _ in range(2)]  
    score[0][0] = arr[0][0]  
    score[1][0] = arr[1][0]  
    for i in range(1, n):  
        if i == 1:  
            score[0][i] = score[1][i - 1] + arr[0][i]  
            score[1][i] = score[0][i - 1] + arr[1][i]  
        else:  
            score[0][i] = max(score[1][i - 1], score[1][i - 2]) + arr[0][i]  
            score[1][i] = max(score[0][i - 1], score[0][i - 2]) + arr[1][i]  
  
    print(max(score[0][n - 1], score[1][n - 1]))

메모리 줄이기

정답은 통과가 됐지만, 점화식을 따라가다 보면 score 배열을 따로 선언하지 않아도 되는 것을 알 수 있다. i-1, i-2의 정보만 저장하는 변수를 통해 메모리를 줄여보겠다.

2차 풀이

import sys  
  
input = sys.stdin.readline  
  
t = int(input())  
for _ in range(t):  
    n = int(input())  
    arr = [list(map(int, input().split())) for _ in range(2)]  
    now_top = arr[0][0]  
    now_bot = arr[1][0]  
  
    prev_top = 0  
    prev_bot = 0  
  
    for i in range(1, n):  
        new_top = max(now_bot, prev_bot) + arr[0][i]  
        new_bot = max(now_top, prev_top) + arr[1][i]  
  
        prev_top, prev_bot = now_top, now_bot  
        now_top, now_bot = new_top, new_bot  
  
    print(max(now_top, now_bot))