728x90
코드 힌트
- 문제 분석:
- 스티커들이 원형으로 연결되어 있어서, 첫 번째 스티커를 떼면 마지막 스티커는 뗄 수 없습니다. 반대로 첫 번째 스티커를 떼지 않으면 마지막 스티커까지 떼는 것이 가능합니다.
- 따라서 첫 번째 스티커를 떼는 경우와 떼지 않는 경우로 나누어 동적 계획법(DP)을 사용해 최댓값을 구하는 문제입니다.
- 두 가지 케이스로 나눔:
- 첫 번째 스티커를 떼는 경우:
- 첫 번째 스티커를 떼었으므로 마지막 스티커는 뗄 수 없습니다.
- 즉, 마지막 전 스티커까지 고려하여 최댓값을 구합니다.
- 첫 번째 스티커를 떼지 않는 경우:
- 첫 번째 스티커를 떼지 않았으므로 마지막 스티커까지 포함하여 최댓값을 구할 수 있습니다.
- 첫 번째 스티커를 떼는 경우:
- 동적 계획법(DP) 기본 아이디어:
- DP 배열은 각 스티커를 선택할 때 얻을 수 있는 최댓값을 저장하는 배열입니다.
- DP 배열의 인덱스 i는 스티커 배열에서 i번째 스티커를 선택할 때까지 얻을 수 있는 최대 스티커 합을 의미합니다.
- dp[i] = max(dp[i-1], dp[i-2] + sticker[i]): i번째 스티커를 떼지 않을 경우는 이전 스티커까지의 최대 값인 dp[i-1], i번째 스티커를 뗄 경우는 dp[i-2] + sticker[i]를 계산하여 두 값 중 더 큰 값을 선택합니다.
- 첫 번째 스티커를 떼는 경우:
- 첫 번째 스티커를 떼었으므로, dp1[0]은 무조건 첫 번째 스티커의 값입니다.
- dp1[1]도 첫 번째 스티커를 떼었기 때문에, 두 번째 스티커는 뗄 수 없습니다. 따라서 dp1[1] = dp1[0]입니다.
- 이후 dp1[i]는 마지막 스티커를 제외하고, 각 스티커를 떼는 경우와 떼지 않는 경우를 비교하여 최댓값을 갱신합니다.
- 첫 번째 스티커를 떼지 않는 경우:
- 첫 번째 스티커를 떼지 않기 때문에, dp2[0] = 0입니다.
- 두 번째 스티커부터 고려할 수 있으므로, dp2[1] = sticker[1]로 설정합니다.
- 이후 마지막 스티커까지 각 스티커를 떼는 경우와 떼지 않는 경우를 비교하여 dp2[i]를 계산합니다.
- 최종 결과:
- 첫 번째 스티커를 떼는 경우는 마지막 전 스티커까지의 결과인 dp1[n-2]와 비교하고, 첫 번째 스티커를 떼지 않는 경우는 마지막 스티커까지의 결과인 dp2[n-1]을 비교하여 최댓값을 반환합니다.
1. dp1[n-2]인 이유 (첫 번째 스티커를 떼는 경우)
- 첫 번째 스티커를 뗐을 경우, 마지막 스티커는 뗄 수 없습니다.
- 따라서 마지막 스티커 전인 n-2번째 스티커까지 최댓값을 계산하게 됩니다.
- 즉, dp1[n-2]는 첫 번째 스티커를 뗀 상태에서 마지막 전 스티커까지의 최대값을 의미합니다.
- 마지막 스티커는 선택할 수 없으니, dp1[n-1]은 계산하지 않습니다.
2. dp2[n-1]인 이유 (첫 번째 스티커를 떼지 않는 경우)
- 첫 번째 스티커를 떼지 않으면, 마지막 스티커까지 뗄 수 있습니다.
- 따라서 마지막 스티커까지 고려한 최댓값을 구할 수 있으므로 dp2[n-1]이 사용됩니다.
- 즉, dp2[n-1]은 첫 번째 스티커를 뗄 수 없는 상황에서 마지막 스티커까지 포함한 경우의 최댓값을 의미합니다.
최종 결과 비교
- 첫 번째 스티커를 떼면 마지막 스티커는 뗄 수 없으니 dp1[n-2]까지의 최댓값을 구하고,
- 첫 번째 스티커를 떼지 않으면 마지막 스티커까지 계산하므로 dp2[n-1]까지의 최댓값을 구합니다.
- 이렇게 두 가지 경우를 비교해 더 큰 값을 결과로 반환하게 됩니다.
요약
- 첫 번째 스티커를 뗐을 때: 마지막 스티커는 뗄 수 없기 때문에 dp1[n-2]까지 고려.
- 첫 번째 스티커를 떼지 않았을 때: 마지막 스티커까지 뗄 수 있어 dp2[n-1]까지 고려.
정답은 더보기 클릭
더보기
class Solution {
public int solution(int sticker[]) {
int n = sticker.length; // 스티커의 총 개수
// 스티커가 1개일 경우, 해당 스티커 값이 답이므로 바로 반환
if (n == 1) return sticker[0];
// 두 가지 경우에 대한 dp 배열 선언
int[] dp1 = new int[n]; // 첫 번째 스티커를 떼는 경우
int[] dp2 = new int[n]; // 첫 번째 스티커를 떼지 않는 경우
// dp1 배열 초기값 설정
dp1[0] = sticker[0]; // 첫 번째 스티커를 떼는 경우, 첫 번째 값은 무조건 포함
dp1[1] = sticker[0]; // 두 번째 스티커는 첫 번째를 떼면 뗄 수 없음
// 첫 번째 스티커를 뗀 경우, n-1번 스티커는 떼지 않으므로 n-2까지 처리
for (int i = 2; i < n - 1; i++) {
dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i]); // 전 스티커를 떼는 것과 i번째 스티커를 떼는 것 중 큰 값 선택
}
// dp2 배열 초기값 설정
dp2[0] = 0; // 첫 번째 스티커는 떼지 않으므로 0으로 설정
dp2[1] = sticker[1]; // 두 번째 스티커는 첫 번째를 안 뗀 상태에서 떼므로 값은 그대로
// 첫 번째 스티커를 떼지 않는 경우는 마지막 스티커까지 고려 가능
for (int i = 2; i < n; i++) {
dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i]); // 이전 스티커를 떼거나 현재 스티커를 뗀 것 중 큰 값 선택
}
// 두 경우 중 최댓값 반환: 첫 번째 스티커를 뗀 경우 마지막 전까지 비교, 떼지 않은 경우 마지막까지 비교
return Math.max(dp1[n-2], dp2[n-1]);
}
}
728x90
'프로그래머스(Java) > Level 3' 카테고리의 다른 글
[프로그래머스] 불량 사용자 (0) | 2024.10.16 |
---|---|
[프로그래머스] 기지국 설치 (1) | 2024.09.13 |
[프로그래머스] 단속카메라 (0) | 2024.09.05 |
[프로그래머스] 최고의 집합 (0) | 2024.09.03 |
[프로그래머스] 숫자 게임 (0) | 2024.09.03 |