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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12971

프로그래머스

해당 문제는 DFS를 사용하려 했으나 경우의 수가 십 만이 넘으므로 DP를 사용하여 해결하였다.

스티커가 원형으로 이어져 있기 때문에 첫번째 스티커를 뽑을 때와 그렇지 않을 때의 DP 테이블을 만들어준다.

그리고 각각의 경우에서 스티커를 뽑을 때와 뽑지 않을 때를 나누어서 각각의 더한 값을 구하고 그 중에서 최댓값을 DP의 값으로 넣어준다.

예를 들어서 첫번째 스티커를 뽑는 경우, sticker 1, 2, 3, 4, 5에서 DP[0]은 첫번째 숫자를 뽑았기에 DP[0] = sticker[0]이되고 DP[1]는 sticker[1]을 뽑을 수 없기 때문에 DP[1] = DP[0]가 된다.

계속해서 DP[2]는 해당 인덱스의 스티커를 뽑느냐(DP[1] + sticker[2]) 뽑지 않느냐(DP[1]) 중에서 큰 값을 대입한다.

첫번째 스티커를 뽑기 때문에 마지막 스티커는 뽑을 수 없다.

따라서 len(sticker)-1까지 해당 과정을 반복한다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. sticker 배열의 길이가 1일 경우에 뽑을 수 있는 경우의 수는 하나 밖에 없으므로 이를 반환해준다.

2. 첫번째 스티커를 뽑는 지에 따라서 두 개의 DP 테이블을 만들어준다.

3. 각각의 경우에 따라서 스티커를 뽑았을 때의 합과 그렇지 않았을 때의 합을 비교하여 큰 값을 DP 값에 넣어준다.

4. 두 DP 테이블 값 중 큰 값을 반환한다.

 

def solution(sticker):
    if len(sticker) == 1: #1번
        return sticker[0]
    
#2번
    one = [0 for _ in range(len(sticker))]
    two = [0 for _ in range(len(sticker))]
    
#첫번째 스티커를 뽑는 경우
    one[0] = sticker[0]
    one[1] = one[0]
    for i in range(2, len(sticker)-1):
        one[i] = max(one[i-2]+sticker[i], one[i-1]) #3번
    
#첫번째 스티커를 뽑지 않는 경우
    for i in range(1, len(sticker)):
        two[i] = max(two[i-2]+sticker[i], two[i-1]) #3번

    return max(one[-2], two[-1]) #4번 : one의 경우, 마지막 스티커를 뽑을 수 없기 때문에 뒤에서 두번째 값을 사용해야한다.

 

첫번째 스티커를 뽑느냐에 따라서 2가지 경우를 생각하고 또 그중에서 스티커를 뽑느냐에 따라서 2가지 경우를 또 생각해야하는 문제였기에 쉽지는 않았다.

또한 두번째 경우에서 최댓값을 찾는 데 시간을 많이 쓴 문제였다.

첫 답안 제출 시, 효율성은 모두 맞았으나 정확성 문제 중 1개만 런타임 에러가 발생한 것을 확인할 수 있었다.

효율성이 맞았는데, 정확성이 시간 초과가 난 것에 상당히 당황했었다.

하지만 해당 코드는 길이가 1일 때는 사용하지 적합하지 않다는 것을 깨닫고 따로 분류하여 반환할 수 있게 코드를 작성하여 성공할 수 있었다.

언제나 그렇지만 가장 먼저 분류할 수 있는 경우를 미리 작성하여 빼놓는 것도 중요한 요인이다. (앞으로 빼먹지 말아야징 ㅎ)

그리고 경우의 수가 큰 경우에는 DFS와 같은 재귀 호출보다는 DP를 우선적으로 사용해야겠다.