[programmers] 스티커 모으기(2) - Java
- 원형으로 연결된 스티커에서 인접하지 않은 스티커를 선택하여 최대 합을 구하는 문제
- 첫 번째 스티커 선택 여부에 따라 두 가지 경우로 나누어 계산
- 동적 프로그래밍을 사용하여 각 위치까지의 최대 합을 계산
- 점화식 dp[i] = max(dp[i-1], dp[i-2] + sticker[i])을 활용하여 최적해 도출
Dec 16, 2024
스티커 모으기(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로 최대가 됩니다.
solution.java
class Solution { public int solution(int sticker[]) { int n = sticker.length; // 스티커가 하나만 있는 경우, 해당 값을 반환 if (n == 1) { return sticker[0]; } // 첫 번째 스티커를 포함하고 마지막 스티커는 제외하는 경우 int maxSum1 = calculateMaxSum(sticker, 0, n - 2); // 첫 번째 스티커를 제외하고 마지막 스티커는 포함하는 경우 int maxSum2 = calculateMaxSum(sticker, 1, n - 1); // 두 경우의 최대값 반환 return Math.max(maxSum1, maxSum2); } // 선형 배열에서 최대 합을 계산하는 함수 // dp[i]는 인접한 스티커를 선택하지 않았을 때, 인덱스 i까지의 최대 합계 public int calculateMaxSum(int[] arr, int start, int end) { int[] dp = new int[end - start + 1]; dp[0] = arr[start]; if (end - start > 0) { dp[1] = Math.max(arr[start], arr[start + 1]); } for (int i = 2; i <= end - start; i++) { dp[i] = Math.max(dp[i - 1], dp[i - 2] + arr[start + i]); } return dp[end - start]; } }
핵심 키워드
- 첫 번째 스티커를 선택하는 경우와 선택하지 않는 경우로 나눠서 계산한다.
- 동적 프로그래밍을 적용해서 배열의 값을 순회할 때 이전 인덱스의 합을 유지하는게 더 값이 높은지 아니면 새로운 인덱스의 합을 구하는 것이 높은지 계산한다.
dp[i]
는i
번째 스티커까지 고려했을 때 최대 합을 의미한다.- 점화식:
dp[i] = max(dp[i-1], dp[i-2] + sticker[i])
dp[i-1]
: 현재 스티커를 선택하지 않는 경우.dp[i-2] + sticker[i]
: 현재 스티커를 선택하는 경우.
결론!
해당 문제를 통해서 동적프로그래밍을 이해할 수 있었다.
Share article