[백준] 9465 스티커 - 실버 1

[오늘의 문제]

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

---

[오늘의 학습 키워드]

• DP
• 구현

---

1. 문제설명

 

주어진 스티커는 낡은 스티커라 하나의 스티커를 떼면 주변에 인접한 4방향의 스티커가 찢어져 사용할 수 없다.

 

따라서 스티커별로 점수를 매겨서 점수의 합이 가장 높아지게끔 스티커를 뜯으려 한다.

 

N이 주어질 때, 2 x N 크기의 스티커의 점수의 최댓값을 구하는 프로그램을 작성하는 문제입니다.

---

[제한사항]

• 시간 제한 1초
• 메모리 제한 256MB
• 1 ≤ N ≤ 100,000

---

2. 접근방식

 

이번 문제를 해결하기 위해서는 점화식을 세우는 방식이 중요합니다.

 

스티커가 2 x N 장 주어질 때 스티커를 선택하는 방법중 최대값을 구하는 방법을 선택해야 합니다.

 

N이 1이 주어진 경우부터 살펴 보겠습니다.

 

 

N이 1인 경우 스티커는 위 그림과 같이 주어지게 되는데 두 스티커 중 하나를 뜯는 경우 나머지 스티커는 사용할 수 없게 되죠

 

따라서 두 스티커 중 더 값이 큰 스티커를 선택하면 될 겁니다.

 

N이 2가 주어진 경우 살펴 보겠습니다.

 

 

N이 2가 주어진 경우 스티커는 두 가지 방식으로 선택할 수 있습니다.

 

서로 이웃하지 않는 대각선 방향의 스티커를 선택해 떼면 되는 것이죠

 

N번째 스티커를 뗄때 최댓값이어야 하므로 두 선택 중 값이 더 큰 값을 선택해서 뜯으면 되는 것입니다.

 

N이 가장 큰 값이라 해도 무조건 앞에 있는 대각선 값을 더하는게 더 큰 값이 되기 때문이죠

 

N이 3이 주어진 경우 스티커를 뜯는 방법을 보겠습니다.

 

 

이렇게 4가지 방법이 존재하죠 

 

그 중 2가지 방법은 기존의 방식과 동일한 진행 방식 입니다.

 

새로이 2가지 방식이 추가되었는데 바로 이전 대각선이 아닌 그 이전의 2번째 대각선에 N을 선택하는 경우 입니다.

 

이 경우 중간의 값을 사용하지 못하는데 중간값을 이용하여 N을 선택하는 경우보다

 

2번째 대각선에 존재하는 값이 더 큰 경우 이 방식을 활용해 주어야 겠죠

 

그렇다면 2번째 대각선에 존재하는 값이 중간값보다 큰 경우를 살펴보러면

 

 

노란색으로 칠해진 두 값을 비교해 주어야 겠죠

 

현재 N이 3 이므로 N이 2까지 일때 

 

 

이 노란색 값은 

 

 

이렇게 두 값의 합과 같습니다.

 

앞서 N이 2일때 이런 방식으로 중간값을 선택했기 때문이죠

 

그러면 우리가 비교하려는 값은

 

이 두값의 비교와 동일하겠죠

 

그런데도 녹색의 값이 더 크다면 

 

N 번째 스티커를 선택할 때 두번째 전 대각선의 값을 선택하게 되는 것입니다.

 

이렇게 비교과 완료되었다면 N번째 스티커의 값이 결정되죠

 

즉 이 점화식은 N이 3이상일 때 부터 제대로 동작이 가능한 점화식인 것입니다.

 

따라서 N이 1이거나, N이 2인 경우는 따로 값을 처리해주고 N이 3일때 부터 비교방식을 통해 더 큰 값을 선택해 나가면 되겠죠

 

그럼 이 식을 코드로 세워보겠습니다.

 

---

3. 코드

import sys
input = sys.stdin.readline

# 테스트케이스
T = int(input())
for _ in range(T):

    # 입력
    N = int(input())
    stickers = [list(map(int, input().split())) for _ in range(2)]

    # DP 테이블 생성
    DP = [[0] * N for _ in range(2)]

    # DP 테이블 초기화
    DP[0][0] = stickers[0][0]
    DP[1][0] = stickers[1][0]
    if N == 1:
        print(max(DP[0][0], DP[1][0]))
        continue

    DP[0][1] = stickers[1][0] + stickers[0][1]
    DP[1][1] = stickers[0][0] + stickers[1][1]
    if N == 2:
        print(max(DP[0][1], DP[1][1]))
        continue

    # 점화식 토대로 값 선택하기
    for i in range(2, N):
        DP[0][i] = max(DP[1][i - 2], DP[1][i - 1]) + stickers[0][i]
        DP[1][i] = max(DP[0][i - 2], DP[0][i - 1]) + stickers[1][i]

    print(max(DP[0][N - 1], DP[1][N - 1]))

---

[코드설명]

 

N이 3 이상인 경우부터 유효하게 비교가 가능한 방식이니 N이 1이거나 N이 2일때 따로 값을 초기화 해주어야 합니다.

 

그와 별개로 DP 테이블은 초기화 되어야 겠죠

 

따라서

    # DP 테이블 생성
    DP = [[0] * N for _ in range(2)]

    # DP 테이블 초기화
    DP[0][0] = stickers[0][0]
    DP[1][0] = stickers[1][0]
    if N == 1:
        print(max(DP[0][0], DP[1][0]))
        continue

    DP[0][1] = stickers[1][0] + stickers[0][1]
    DP[1][1] = stickers[0][0] + stickers[1][1]
    if N == 2:
        print(max(DP[0][1], DP[1][1]))
        continue

 

이러한 방식으로 DP 테이블을 초기화 해주고 N이 1이거나 2인 경우 따로 값을 출력해 주었습니다.

 

N이 3 이상인 경우 앞서 조건을 토대로 값을 비교해 주어야겠죠

 

 

이 그림에서 알 수 있듯이 1번 선택과 2번 선택으로 값이 달라집니다.

 

1번을 선택하기 위해서는 비교값 중 가운데 값이 더 커야 합니다.

 

2번을 선택하기 위해서는 비교값 중 첫번째 값이 더 커야겠죠

 

우리가 목표로 하는 파란색 위치의 값을 계산하기 위해서 말입니다.

 

    # 점화식 토대로 값 선택하기
    for i in range(2, N):
        DP[0][i] = max(DP[1][i - 2], DP[1][i - 1]) + stickers[0][i]
        DP[1][i] = max(DP[0][i - 2], DP[0][i - 1]) + stickers[1][i]

 

따라서 현재 내가 선택하려는 값은 두 값을 비교한 값에 현재 위치의 값을 더해준 값이 되겠죠

 

앞선 초기화를 통해 중간값은 처음값과 중간값의 합으로 설정되어 있기 때문에 가능한 비교방식 입니다.

 

1번을 선택한다면 대각선 값을 선택하는 경우의  수가 유지되는 것이고

 

2번을 선택한다면 규칙이 깨지는 선택이 되겠죠

 

즉 이 2줄의 코드를 통해서 

 

 

이 4가지의 경우의 수를 모두 구할 수 있는 것입니다.

 

이 모든 조건을 만족하기 위해서는 2줄의 DP 테이블이 필요하고 적절한 초기화가 필요합니다.

 

또한 주어진 테스트케이스 속에서 동작하여야 하므로 최종 코드는 처음 작성한 코드가 되는 것입니다.

---

4. 결과

---

[회고]

 

이번 문제는 해결하는데 시간이 오래 걸리지는 않았습니다.

 

주어진 조건을 손으로 풀어보며 적절한 경우의 수를 찾았기 때문입니다.

 

 

손으로 먼저 조건을 생각해 보았죠

 

N이 주어진 경우 최대값을 선택하는 모양은 N이 3 이상인 경우 모양이 달라졌습니다.

 

더 자세히 나눠보면 스티커는 결국 2 x N 크기의 스티커가 제공되니 DP 테이블도 2줄이 필요했습니다.

 

또 1번줄과 2번줄을 선택할 때 모양은 결국 2개 뿐이죠

 

대각선 선택이냐, 2번째 대각선 선택이냐 이 2가지 경우 뿐이었습니다.

 

이 두가지 경우의 수를 구하기 위해서는 결국 2번째 대각선이 더 큰 값이냐, 대각선 값이 더 큰 값이냐에 따라 달라지는 것이었습니다.

 

따라서 DP[0][i] = max(DP[1][i - 2], DP[1][i - 1]) + DP[0][i] 와 같은 식을 세울수 있었죠

 

손으로 풀어 조건을 확인하고 나니 어렵지 않게 문제를 해결할 수 있었습니다.