N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단, 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다. 예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다.
스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.
2. 제한사항
● sticker는 원형으로 연결된 스티커의 각 칸에 적힌 숫자가 순서대로 들어있는 배열로, 길이(N)는 1 이상 100,000 이하입니다. ● sticker의 각 원소는 스티커의 각 칸에 적힌 숫자이며, 각 칸에 적힌 숫자는 1 이상 100 이하의 자연수입니다. ● 원형의 스티커 모양을 위해 sticker 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어있다고 간주합니다.
3. 입출력 예시
sticker
return
[14,6,5,11,3,9,2,10]
36
[1,3,2,5,4]
8
4. 나의풀이
스티커의 0번과 마지막 방의 원소가 연결되어 있는 구조.
i번째 스티커를 뜯으면 양쪽 스티커는 사용할 수 없는 구조 - 0번이면 마지막 방의 스티커는 사용할 수 없음. - 1번이면 마지막 방의 스티커를 사용할 수 있음.
그래서 0번 스티커를 사용한 경우와 1번 스티커를 사용한 경우를 비교해서 더 큰 값을 리턴하면 됨.
Point !! - dp(동적프로그래밍) 문제라고 생각함. - i번째 스티커를 사용했을 때 i+2 스티커를 사용할 것이냐, i+3 스티커를 사용할 것이냐를 판단해야 함. -그러기 위해서 더하기 전의 숫자를 저장하고, 그 숫자에 각각 더하여 더 큰 값을 저장해야 함.
궁금증?? - 만약 내가 0번 스티커로 시작했다고 했을 때, 1번은 무시하고 2번,3번 혹은 4번까지 고민할 수도 있음. - 4번이 2,3번보다 더 큰 수라고 했을 때, 2번을 골라야 4번을 고를 수 있음. 그냥 0번에서 4번을 고르면 2번+4번보다 더 작을 수 밖에 없음. - 그런데 0+2번보다 0+3번이 더 크다? 그러면 4번을 고를 수가 없음. - 그래서 만약 i가 4일 때, i-2번방에는 0+2번 수를, i-1번방에는 0+2번 수와 0+3번 수 중 더 큰 수를 저장하면 됨.
- 위 예제로 설명하면, 스티커와 길이가 같은 dp배열을 선언하고, dp[0]과 dp[1]에 14를 저장. i = 2일 때, i-2번방 즉 dp[0]의 수인 14에 2번스티커인 5를 더한 19를 i-1번방 즉 dp[1]과 비교하여 더 큰 수를 dp[2]에 저장. i = 3일 때, i-2번방 즉 dp[1]의 수인 14에 3번스티커인 11을 더한 25를 dp[2]와 비교하여 더 큰 수를 dp[3]에 저장. >> 이러면 3번 스티커를 더한 25가 dp[3]에 저장될 것이고 이 경우에는 3번 테크로 가게 되는 거임. 매 번 비교할 때마다 테크가 변함.
[C# 코드]
public int solution(int[] sticker)
{
int answer = 0;
//스티커의 양옆은 사용할 수 없으므로 스티커가 3개 이하면 가장 큰 값을 리턴.
if (sticker.Length <= 3)
return sticker.Max();
//시작이 0번이냐 1번이냐로 갈림.
//스티커의 0번방부터 시작하는 배열.
var dp1 = new int[sticker.Length];
//스티커의 1번방부터 시작하는 배열.
var dp2 = new int[sticker.Length];
dp1[0] = sticker[0];
dp1[1] = sticker[0];
for (int i = 2; i < dp1.Length-1; i++)
{
if(dp1[i-1] < sticker[i] + dp1[i - 2])
{
dp1[i] = sticker[i] + dp1[i - 2];
}
else
{
dp1[i] = dp1[i - 1];
}
}
dp2[0] = 0;
dp2[1] = sticker[1];
for (int i = 2; i < dp2.Length; i++)
{
if (dp2[i - 1] < sticker[i] + dp2[i - 2])
{
dp2[i] = sticker[i] + dp2[i - 2];
}
else
{
dp2[i] = dp2[i - 1];
}
}
//dp1은 dp1.Length-1만큼 for문이 돌았으니 dp1.Length - 2의 수를 비교.
//dp2는 dp2.Length만큼 for문이 돌았으니 dp2.Length - 1의 수를 비교.
if (dp1[dp1.Length - 2] > dp2[dp2.Length - 1])
answer = dp1[dp1.Length - 2];
else
answer = dp2[dp2.Length - 1];
return answer;
}
