[프로그래머스] 스티커 모으기(2) - (Summer/Winter Coding(~2018))
https://programmers.co.kr/learn/courses/30/lessons/12971
코딩테스트 연습 - 스티커 모으기(2)
N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록
programmers.co.kr
2021-10-30
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution {
public static int solution(int sticker[]) {
int[][] dp = new int[sticker.length][2];
dp[0][0] = 0; // 0 : 첫번째 스티커를 뜯지 않는 경우
dp[0][1] = sticker[0]; // 1 : 첫번째 스티커를 뜯는 경우
if(sticker.length >= 2) {
dp[1][0] = sticker[1];
dp[1][1] = dp[0][1];
}
for(int i = 2; i < sticker.length; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-2][0] + sticker[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-2][1] + sticker[i]);
}
if(sticker.length == 1) return sticker[0];
return Math.max(dp[sticker.length-1][0], dp[sticker.length-2][1]);
}
}
|
cs |
#문제풀이
dp문제
dp[i][0] 에는 가장 첫번째 스티커를 뜨지 않은 경우들을 저장할 것이고,
dp[i][1] 에는 가장 첫번째 스티커를 뜯은 경우들을 저장한다.
그래서 dp[i][0] 에서는
dp[i-1][0] (바로 전까지 저장한 합)과 dp[i-2][0] + sticker[i] (전전까지 저장한 합 + 지금 현재 스티커를 뜯었을 때의 합) 2개를 비교해서 더 큰 수를 저장한다.
마찬가지로 dp[i][1]에서는
dp[i-1][1] (바로 전까지 저장한 합)과 dp[i-2][1] + sticker[i] (전전까지 저장한 합 + 지금 현재 스티커를 뜯었을 때의 합) 2개를 비교해서 더 큰 수를 저장한다.
마지막으로,
첫번째 스티커를 뜯지 않은 경우 dp[sticker.legnth-1][0]과 첫번째 스티커를 뜯은 경우 dp[sticker.length-2][1] (마지막은 뜯을 수 없음) 두 가지를 비교해서 더 큰 값을 출력해주면 된다.
그리고 sticker의 length에 따라 조건을 나눠준 이유는 조건 상 길이(N)이 2이상이 아니라 1 이상이라고 명시했기 때문이다.
(반례로 라인 17번 지우면 33번에서 런타임 에러난다.)
