스티커 모으기(2) : https://school.programmers.co.kr/learn/courses/30/lessons/12971
Problem
Solve
한번에 캐치못하고 다른 분들의 풀이에서 힌트를 보고 해결했던 문제입니다. (접근 방법을 생각하는 과정에서 DP를 배제해버렸었네요..)
먼저 해당 스티커를 사용하는지 안하는지에 대한 점화식을 세워보겠습니다.
sticker[i]를 사용하는 경우 이전에 위치한 스티커를 사용하지 못합니다.- 반대로
sticker[i]를 사용하지 않는 경우 이전에 위치한 스티커를 사용합니다. sticker[i]를 사용할지는 위 두가지 경우를 비교하여 큰값의 경우를 선택하게 됩니다.dp[i]에 해당 스티커를 사용한것과 이전 스티커를 사용한것과 비교한 것 중 큰값을 저장합니다.- 이전 스티커를 사용한다면
dp[i] = dp[i-1]이 됩니다.- 이전 스티커에서의 값 그대로 사용
- 현재 스티커를 사용한다면
dp[i] = dp[i-2] + sticker[i]가 됩니다.- 이전 스티커를 사용하지 않고 이전 스티커의 이전 스티커의 값과 현재 스티커의 값으로 갱신해줍니다.
즉, 이전 스티커를 사용하는 경우와 현재 스티커를 사용하는 경우를 비교하기 위해서
dp[i] = Math.max(dp[i-1], dp[i-2]+sticker[i])라는 점화식이 세워지게 됩니다.
주어진 배열 sticker에서 선택한 sticker[i]의 양 옆의 스티커를 사용할 수 없다고 했습니다.
그렇기 때문에 이 접근법을 사용하기 위해서는 첫번째 스티커를 사용하는지, 사용하지 않을지에 대해 두가지 경우를 생각해야합니다.
첫번째 스티커를 사용하는 경우는 dp[0] = sticker[0]과 dp[1] = sticker[0]으로 초기화 해줍니다.
그리고 sticker[2]부터 비교하며 이전 스티커의 값 dp[1]과 더 이전의 스티커 값 dp[0]+sticker[2]의 값을 비교하여 더 큰값을 dp[2]에 저장하는 식으로 반복해줍니다.
첫번째 스티커를 사용하지 않는 경우는 dp[0] = 0, dp[1] = sticker[1]으로 초기화 해주고 위와 같이 동일하게 반복해줍니다.
이때, 각 dp가 가지는 최대값이 answer가 됩니다.
주의할 점이라면 sticker의 길이가 1, 2, 3이상일때의 answer를 잘 고려하고 값을 반환하거나 초기화 해주셔야 합니다.
Code
class Solution {
public int solution(int sticker[]) {
int answer = 0;
int N = sticker.length;
int[] dp1 = new int[N];
int[] dp2 = new int[N];
//1개의 스티커만 주어진 경우
if(N==1) return sticker[0];
//첫번째 스티커를 사용한 경우
dp1[0] = sticker[0];
dp1[1] = sticker[0];
for(int i=2;i<N-1;i++){
dp1[i] = Math.max(dp1[i-1],dp1[i-2]+sticker[i]);
}
//첫번째 스티커를 사용하지 않은 경우
dp2[0] = 0;
dp2[1] = sticker[1];
answer = Math.max(sticker[1],answer);
for(int i=2;i<N;i++){
dp2[i] = Math.max(dp2[i-1], dp2[i-2]+sticker[i]);
}
//dp1은 첫번째 스티커를 사용했기 때문에 마지막 사용가능한 스티커는 N-2
//dp2는 첫번째 스티커를 사용했기 떄문에 마지막 사용가능한 스티커는 N-1
answer = Math.max(dp1[N-2],dp2[N-1]);
return answer;
}
}Result
Reference
