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

문제 링크

스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게 된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.

문제에 제시된 조건과 요구 결과이다. 최대 점수를 얻을 수 있도록 스티커를 떼야한다. 처음엔 공유하는 스티커가 찢어져 사용할 수 없으니 BFS인가..? 했는데 전혀 아니었고, 그럼 그리디인가..? 했는데 무조건 높은 점수를 더해가면 나중에 틀리는 반례가 있었다. 즉, 모든 스티커에 방문할 때마다 최댓값을 비교하며 변경해야 하는 다이내믹 프로그래밍이었다.

 

예시를 통해 그리디가 아닌 이유를 알 수 있다. 문제를 잘 읽어보면 보통 대각선 스티커를 선택하는 게 당연해 보인다. 하지만 예시서 대각선을 따라가면 틀린다.

대각선 : 50 ➡️ 50 ➡️ 100 ➡️ 10 ➡️ 40 == 250
실제 최댓값 : 50 ➡️ 50 ➡️ 100 ➡️ 60 == 260

굳이 대각선에 있는 스티커가 아니라 한 칸 떨어져 있는 스티커를 더해줘도 답이 된다.

 

고려해야 할 경우

• n == 1일 때
  • max(윗줄 0번 인덱스, 아랫줄 0번 인덱스)
• n == 2일 때 ➡️ 대각선 접근만 가능
  • max((윗줄 0번 인덱스 + 아랫줄 1번 인덱스), (윗줄 1번 인덱스 + 아랫줄 0번 인덱스))
• n >= 3일 때
  • 대각선을 번갈아가며 마지막 인덱스까지 가는 경우
  • 인덱스를 하나 건너뛰어 더해줄 경우 ➡️ 문제에 나온 예시가 이 경우임

 

코드 설명

1. 우선 입력값을 저장하고 dp 메서드를 호출한다.

메서드 반환값을 바로 출력하도록 했다. 이때 반환값은 최대 점수이다.

 

 

2. 점화식 값을 저장할 dp 리스트를 선언한다.

어차피 0번 인덱스부터 시작하기 때문에 n+1이 아닌 n칸으로 만들어줘도 된다.

 

 

3. n == 1일 때

단순하다. 윗줄과 아랫줄이 모두 한 칸씩 갖고 있기 때문에 두 값을 비교하여 최댓값을 반환하면 된다.

 

 

4. n == 2일 때

이 경우도 윗줄과 아랫줄이 각각 두 칸씩 갖고 있기 때문에 대각선으로 더하는 경우밖에 없다. 대각선으로 더해 나온 두 값 중 최댓값을 반환한다.

 

 

5. n >= 3일 때 (메인 로직)

⭐️ 이 반복문은 n == 1일 때와 n == 2일 때 d[0][0], d[1][0], d[0][1], d[1][1]에 저장한 값을 기반으로 시작한다. d[i][i-1]은 한 칸 떨어진 값이다. d[1][i-1]은 위 코드에서 대각선끼리 더한 값이다. 즉, 한 칸 떨어진 값을 더하는 게 큰지, 아니면 대각선으로 더해가는 게 큰지 비교하는 로직이다.

 

d[0][i]은 윗줄 0번 인덱스부터 시작하는 점화식이고, d[1][i]는 아랫줄 0번 인덱스부터 시작하는 점화식이다. 반복문이 끝나면 윗줄과 아랫줄 마지막 인덱스 값 중 더 큰 값을 반환한다.

 

 

정답 코드

import sys
input = sys.stdin.readline

def find_max(n, stickers):
    d = [[0] * n for _ in range(2)]

    d[0][0] = stickers[0][0]
    d[1][0] = stickers[1][0]
    if n == 1:
        return max(d[0][0], d[1][0])
    
    d[0][1] = stickers[1][0]+stickers[0][1]
    d[1][1] = stickers[0][0]+stickers[1][1]
    if n == 2:
        return max(d[0][1], d[1][1])

    for i in range(2, n):
        d[0][i] = max(d[1][i - 2], d[1][i - 1]) + stickers[0][i]         
        d[1][i] = max(d[0][i - 2], d[0][i - 1]) + stickers[1][i]
    
    return max(d[0][-1], d[1][-1])


t = int(input())

for _ in range(t):
    n = int(input())
    stickers = []

    for _ in range(2):
        stickers.append(list(map(int, input().split())))

    print(find_max(n, stickers))

 

내가 알고리즘 문제를 풀면서 느낀 그리디와 다이내믹 프로그래밍의 차이점은 다음과 같다.
- 그리디 : 순서대로 가장 최적의 값을 찾아가면 된다. 그저 눈앞에 있는 가장 탐욕적인 답을 선택하면 된다.
- 다이내믹 프로그래밍 : 초반에 탐욕스러운 값이 있더라도 선택하면 안 된다. 뒤에 더 탐욕스러운 값이 기다리고 있기 때문이다. 그리디처럼 눈앞에 보이는 떡을 가져가면 안 되고, 뒤에 있는 값들도 고려해야 한다. 초반에 욕심을 부리면 실제 최적값을 놓친다.