[Coding Test][Python][프로그래머스] Level 3 스티커 모으기(2)

Lv3. 스티커모으기

문제)

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

 

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

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

제한 사항)

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

---

풀이)

※ 풀이 아이디어

1. 처음에 BackTracking으로 접근하였지만 시간초과가 떠서 DP로 풀이방법 변경
2. 처음과 끝이 연결된 DP는 0번째 Element를 포함 시키는 DP Table과 0번째 Element를 포함시키지 않은 DP Table 2개를 관리하여 풀이한다.

DP 풀이

0번째 종이를 뜯는 상황을 가정한 DP Table 1개와 0번째 종이를 뜯지 않는 상황을 가정한 DP Table 1개를 관리하여 풀이한다.

이때, 0번째 종이를 뜯은 상황을 가정한 DP Table은 N-1을 확인하는 것이 아니라 N-2를 확인해야한다.

왜냐하면 max(dp[i-1], dp[i-2] + sticker[i]) 에서 dp[i-2] + sticker[i]가 더 커서 마지막 종이를 뜯는 상황이 나올 수 있기 때문이다.

def solution(sticker):
    answer = 0
    N = len(sticker)
    # Edge Case
    if N == 1:
        return sticker[0]
    
    # 처음과 끝이 이어진 DP에서는 2개의 DP Table 사용
    # 0번째 sticker를 떼었을때
    dp1 = [0] * N
    dp1[0], dp1[1] = sticker[0], sticker[0]
    
    for i in range(2, N):
        # i-1을 떼거나, 2를 떼고 현재를 뗴거나
        dp1[i] = max(dp1[i-1], dp1[i-2] + sticker[i])
        
    # 0번째 sticker를 떼지 않았을 때
    dp2 = [0] * N
    dp2[0], dp2[1] = 0, sticker[1]
    for i in range(2, N):
        dp2[i] = max(dp2[i-1], dp2[i-2] + sticker[i])
        
    answer = max(dp1[N-2], dp2[N-1])
    return answer

DFS 풀이

sticker의 수는 100,000 이하인 것을 생각하지 못하고 DFS로 접근했다가 시간초과가 났다.

def solution(sticker):
    answer = 0
    N = len(sticker)
    visited = [False] * N
    
    def dfs(curr, visited, res):
        global answer
                
        if visited.count(True) == N:
            answer = max(answer, res)

        for i in range(N):
            if visited[i] == False:
                left, right = (i-1) % N, (i+1) % N
                temp = [i]
                visited[i] = True
                if visited[left] == False:
                    visited[left] = True
                    temp.append(left)
                if visited[right] == False:
                    visited[right] = True
                    temp.append(right)
                res += sticker[i]
                dfs(i, visited, res)
                for j in temp:
                    visited[j] = False
                res -= sticker[i]
        
    dfs(0, visited, 0)

    return answer