23.02.28 파이썬 코딩 퀴즈#174 스티커 모으기(2)(프로그래머스 스쿨)

이번 문제는 스티커 모으기(2) 문제이다.

원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내서 최대합을 만들어야 한다. 이 때 한 번 뜯긴 자리 양옆은 찢어져서 사용이 불가능하다.

 

생각해 볼 조합은 3가지 정도이다.

1. 첫번째 스티커를 선택한 후 경우의 수 확인

2. 두번째 스티커를 선택한 후 경우의 수 확인

3. 무작위로 max()값을 찾아서 최대합을 만드는 경우.

 

3번의 경우부터 살펴보면 [99,100,99,1] 을 예를 들어보면 바로 알 수 있다.

첫번째 max()로 100을 선택하면 양 옆의 99를 선택할 수 없다. 따라서 max()를 활용한 최대값은 101이 된다.

 

그렇다면 1,2 번만 생각해서 코드를 작성하면 된다.

해당 문제는 고전적인 dp 문제의 형태를 가진다.

문제 풀이를 위해 먼저 0으로 채워진 dp 배열을 만들고, 첫번째 스티커 즉 index 0을 선택하는 경우를 우선 확인해 보자.

sticker[0] 값을 dp[0]과 dp[1]에 전달한다. 즉 해당 dp는 누적값으로 사용된다는 이야기이다.

그리고 탐색할 범위는 (2, len(sticker)-1)이다. 이미 사용된 index 0 에 의해 0, 1, -1 은 탐색할 필요가 없어졌다.

적절한 값 비교를 위해 [14, 6, 5, 11, 3, 9, 2, 10] 배열을 대입해서 확인해보자.

현재 dp 는 [ 14,14,0,0...] 이다. 그리고 i값은 2부터 시작이다.

dp[1] 과 dp[0]+sticker[2] 값을 비교한다. 즉 현재 dp[2]에서 sticker[2]를 뜯을 것인지 말것인지를 확인하는 것이다.

만약 dp[1] 값이 크다면, sticker[2]는 선택하지 않게 된다. 지금은 14 와 14+5 를 비교하기 때문에 dp[2]값은 19 가 된다.

dp = [14,14,19,0,0,0,0]

 

다음 i가 3이 되었다.

비교할 값은 dp[2] 와 dp[1]+sticker[3] 이다. 19 와 14+11 이므로 sticker[3] 도 뽑게 된다. 따라서 dp[3]은 25 가 된다.

dp = [14,14,19,25,0,0,0,0]

 

다음 i가 4가 되었다.

비교할 값은 dp[3] 과 dp[2]+sticker[4] 이다. 25 와 19+3 이므로 sticker[4]는 뽑지 않는다. 따라서 dp[4]는 25이다.

 

즉 dp의 각 index는 index-1 값과 index-2 + sticker[index] 를 비교하며 누적된값을 전달하게 된다.

dp2 역시 위와 동일하게 적용되며, 한가지 다른점은 탐색 범위가 이번에는 (2, len(sticker))로 마지막 스티커까지 확인한다는 점이다.

 

이렇게 구한 두 값의 max를 비교하여 반환하면 해결된다.