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

문제 보러가기

 

문제 설명

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

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

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

 

제한 사항

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

입출력 예

sticker	answer
[14, 6, 5, 11, 3, 9, 2, 10]	36
[1, 3, 2, 5, 4]	8

 입출력 예 설명

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

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

[문제 풀이]

원형 스티커를 1차원 배열로 표현해서 푸는 것이 간단하다.

이 문제에서 알 수 없는 것이 한가지 있는데, 첫번째 스티커 14를 떼거나 두번째 스티커 6을 떼는 2가지 선택지 중에 어떤 선택지가 최대값이 될지 알 수 없다는 것이다. 그렇기 때문에 14를 떼서 구한 값과 6을 떼서 구한 값, 2가지 결과 값 중에서 최대 값을 써야한다.

또한 최대값을 순차적으로 저장하기 위해서 DP라는 이름의 배열을 사용하여 최대값을 저장한다.

14

6

5

11

3

9

2

10

<첫번째 선택지>

14

6

5

11

3

9

2

10

<두번째 선택지>

[첫번째 선택지]

 

스티커	14	6	5	11	3	9	2	10
DP 배열	14	0	0	0	0	0	0	0

우선 14를 떼고 배열에 저장한다.

 

스티커	14	6	5	11	3	9	2	10
DP 배열	14	14	0	0	0	0	0	0

14를 떼어냈기 때문에 6을 사용할 수 없다. 그래서 배열에 이전값을 저장한다.

 

스티커	14	6	5	11	3	9	2	10
DP 배열	14	14	19	0	0	0	0	0

5로 넘어온다면 2가지 선택지가 생긴다.

11을 쓰기 위해 5를 떼지 않는 선택지와 5를 떼는 선택지가 생긴다.

11을 쓰기 위해 5를 떼지 않는다면 14의 값을 가지게 되고 5를 뗀다면 19의 값을 가지게 된다.

즉 DP[i]가 DP[i-1] 이거나 DP[i-2] + sticker[i]가 된다. 이 중 최대값은 5를 뗀 19의 값이다.

여기서 (i-1)과 (i-2)가 나와서 혼동될 수 있는데, 밑에 예시에서 설명할 수 있다.

 

스티커	14	6	5	11	3	9	2	10
DP 배열	14	14	19	25	0	0	0	0

11로 넘어오는 것 또한 2가지 선택지가 생긴다.

5를 쓰지 않고 11을 뗀 선택지와 5를 뗀 선택지이다.

5를 쓰지 않고 11을 뗀 선택지는 5를 떼지 않았을 때 DP배열의 값 14에 11을 더하는 선택지이고,

5를 뗀 선택지는 5를 떼었을 때 DP배열의 값 19이다. 조금 헷갈릴 수 있는데 간단하게 설명하자면

5를 쓰지 않고 11을 뗀 선택지는 DP[i] = DP[i-2]+stickers[i] 이고 5를 뗀 선택지는 DP[i] = DP[i-1] 이다.

이런 식으로 DP배열에 최대값을 저장하면 되는데 점화식이 DP[i] = Math.max(DP[i-1], DP[i-2] + stickers[i])가 된다.

 

스티커	14	6	5	11	3	9	2	10
DP 배열	14	14	19	25	25	34	34	44

위와 같은 방법으로 DP 배열을 저장하였는데 뭔가 이상한 부분을 발견하였다.

14를 떼었다면 맨 마지막에 위치한 10을 쓸 수 없는데 10의 값이 들어가서 최대값이 44가 되었다.

이러한 문제점 때문에 14를 떼서 시작한 첫번째 선택지의 값은 DP[DP.length-2]가 된다.

 

[두번째 선택지]

 

두번째 선택지는 6을 떼서 시작한 선택지이다.

스티커	14	6	5	11	3	9	2	10
DP 배열	0	6	0	0	0	0	0	0

두번째 선택지와 첫번째 선택지는 출발점이 다르다는 점과 함께 마지막 스티커인 10을 쓸 수 있느냐 없느냐의 차이이다.

점화식  DP[i] = Math.max(DP[i-1], DP[i-2] + stickers[i])를 이용하여 DP배열을 채우는 것은 동일하다.

 

스티커	14	6	5	11	3	9	2	10
DP 배열	0	6	6	17	17	26	26	36

두번째 선택지는 10을 쓸 수 있기 때문에 최대값은 DP[DP.length-1]이 된다.

 

 

[코드]

class Solution {     public int solution(int[] sticker) {         if (sticker.length==1) return sticker[0];         int[] dp = new int[sticker.length + 2];         int first = 0;         int second = 0;         for (int i = 3; i < dp.length; i++) {             dp[i] = Math.max(dp[i - 1], dp[i - 2] + sticker[i - 2]);         }         first = dp[dp.length - 1];         for (int i = 2; i < dp.length; i++) {             dp[i] = Math.max(dp[i - 1], dp[i - 2] + sticker[i - 2]);         }         second = dp[dp.length - 2];         return Math.max(first, second);     } }

문제 풀이대로라면 dp를 선언할 때 int[] dp = new int[stickes.length]; 가 되어야겠지만

dp[0] = Math.max(dp[-1], dp[-2]+stickers[0])이 될 수없는 노릇이라 dp 배열의 길이를 일부러 길게 하였다.