[프로그래머스 lv3] 스티커 모으기(2) (DP 풀이)

Summer/Winter Coding(~2018) 문제입니다.

---

문제 설명

N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.

예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.

제한 사항

• sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다.
• sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다.
• 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1
6, 11, 9, 10이 적힌 스티커를 떼어 냈을 때 36으로 최대가 됩니다.

입출력 예 #2
3, 5가 적힌 스티커를 떼어 냈을 때 8로 최대가 됩니다.

---

나의 풀이

DP 문제는 정말 문제 유형도 다양하고 막상 문제를 보면 DP 문제임을 떠올리기 쉽지 않다.

이 문제도 결국 DP로 해결 가능한 문제였다.

---

이 문제에서 고려해야 할 점은 2개가 있다.

• i번째 스티커를 뜯는 경우
• i번째 스티커를 뜯지 않는 경우

• 첫 번째 스티커를 뜯는 경우
• 첫 번째 스티커를 뜯지 않는 경우

DP문제에서 역시 dp테이블이 등장한다. dp 테이블의 의미를 확실히 해야 문제를 이해하고 풀이하기 용이하다.

이 문제에서 dp 테이블의 i번째 인덱스는 해당 인덱스까지의 최대 점수이다. (i-1번째 스티커를 뜯었는지 안뜯었는지는 알지 못한다)

---

▶ 우선 i번째 스티커를 뜯는 경우

i번째 스티커를 뜯으면 i-1, i+1번째 스티커는 뜯을 수 없다.

DP에서 i번째 경우를 볼 때 i+1번째의 경우는 아직 고려되지 않는다. 그저 i번째까지 왔을 때 최대값이 무엇인가가 중요하다.

만약 i번째 스티커를 뜯었다면 DP[i] = sticker[i] + DP[i-2] 가 될 것이다.

왜냐하면 i번째 스티커를 뜯었기 때문에 i-1번째 스티커는 뜯지 못하기 때문에 i-2까지의 최대값(DP[i-2])에 i번째 스티커의 값을 더하면 된다.

 

▶ i번째 스티커를 뜯지 않는 경우

i번째 스티커를 뜯지 않는 경우는 i-1번째 스티커가 뜯겼는지는 알지 못하지만 DP[i-1]의 값은 i-1번째까지의 최대값이 저 장되어 있기 때문에 DP[i] = DP[i-1] 이 된다.

 

◆ 그래서 i번째 스티커를 뜯었을 때 최대 값은

DP[i] = max(sticker[i] + DP[i-2], DP[i-1]) 가 된다.

---

첫 번째 스티커를 뜯은 경우와 뜯지 않는 경우로 나뉘어질 수 있다.

▷ 첫 번째 스티커를 뜯은 경우

첫 번째 스티커를 뜯은 경우 DP[0]의 값은 sticker[0]이 된다.

그리고 첫 번째 스티커를 뜯으면 두 번째 스티커와 마지막 스티커는 뜯지 못한다. 그렇기 때문에 DP[1]의 값은 DP[0]이 된다. (추가로 점수를 쌓을 수 없기 때문이다)

그렇기 때문에 위에서 구한 DP[i]를 구하는 식을 2번 인덱스 ~ 뒤에서 두 번째 인덱스까지 반복하면 된다.

 

▷ 첫 번째 스티커를 뜯지 않은 경우

첫 번째에 뜯지 않았으므로 DP[0]에 0이 저장된다.

그리고 DP[i]를 구하는 식을 1번 인덱스 ~ 뒤에서 첫 번째 인덱스까지 반복하면 된다.

 

◇ 그래서 이 문제에서 구할 최대값은

첫 번째 스티커를 뜯은 경우와 첫 번째 스티커를 뜯지 않은 경우 중 더 큰 값이 된다.

 

소스 코드

def solution(sticker):
    if len(sticker)==1: return sticker[0]
    
    d1, d2 = [0] * len(sticker), [0] * len(sticker)
    
    # d1은 맨 앞 뜯는 경우
    d1[0] = sticker[0]
    d1[1] = d1[0]
    for i in range(2, len(sticker)-1):
        d1[i] = max(d1[i-2]+sticker[i], d1[i-1])
    
    # d2는 맨 앞 뜯지 않는 경우
    for i in range(1, len(sticker)):
        d2[i] = max(d2[i-2]+sticker[i], d2[i-1])

    return max(d1[-2], d2[-1])

 

테스트 결과