N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다.
원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다.
예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스티커를 뜯어내어 얻을 수 있는 숫자의 합의 최댓값을 return 하는 solution 함수를 완성해 주세요. 원형의 스티커 모양을 위해 배열의 첫 번째 원소와 마지막 원소가 서로 연결되어 있다고 간주합니다.
sticker | answer |
---|---|
[14, 6, 5, 11, 3, 9, 2, 10] | 36 |
[1, 3, 2, 5, 4] | 8 |
조건별로 분기하여 DP로 접근하여 풀 수 있는 문제이다. 먼저 DP로 접근해야 한다는 것을 파악하고, 2가지 경우를 따로 계산해주어야 한다는 것을 캐치한다면 손쉽게 풀 수 있다. (물론 모든 알고리즘 문제가 그렇듯 항상 접근 방법 캐치가 말처럼 쉬운 것은 아니다)
먼저 왜 DP로 접근이 가능한지, 그리고 DP를 가지고 어떻게 접근할 지 이야기 해보자.
문제의 규칙은 요약하면 다음과 같다. 스티커를 한장씩 뜯되 인접한 스티커는 뜯지 못할 때, 얻을 수 있는 최댓값을 구해야 한다. 일단 인접한 스티커라는 조건을 제쳐두고 생각하면, 누적합을 구하는 방식과 굉장히 유사하다는 것을 알 수 있다. 즉 현재 뜯은 스티커 + 다음에 뜯을 스티커
의 누적합이 최댓값이 되는 경우를 찾아야 하는 것이다. 이는 이전에 구해놓은 값을 활용하는 형태가 되므로 중복 계산을 DP를 사용해 최적화 할 수 있을 것이다.
DP로 접근해야겠다고 생각했다면 또 다시 두개의 난관이 남아있다.
1번 부터 보자. 이 경우는 크게 어렵지 않다. 누적합을 구하는 것과 유사하기 때문에 우리는 처음에 스티커의 개수 만큼의 DP 배열을 모두 0으로 초기화해줄 수 있을 것이다. 즉 아래와 같다.
const dp = new Array(sticker.length).fill(0);
그렇다면 우리가 선언한 dp 배열은 다음과 같은 의미를 가질 것이다.
dp[0]
: 첫번째 스티커를 뜯었을 때까지의 누적합dp[1]
: 두번째 스티커를 뜯었을 때까지의 누적합d[[2]
: 세번째 스티커를 뜯었을 때까지의 누적합그렇지만 문제 조건에 의해 누적합은 연달아서 구할 수가 없다. 왜냐하면 인접한 스티커는 뜯을 수 없다는 조건이 있기 때문이다. 게다가 주어진 배열은 일종의 Circular Buffer이기 때문에 배열의 첫과 끝이 서로 이어져 있는 형태로 생각해야 한다. 이 점을 유의하고 일단 점화식을 찾으러 가보자.
일단 첫 번째 스티커를 뜯었다고 생각해보자. 그렇다면 배열의 마지막 스티커와 첫 번째 다음에 있는 두 번째 스티커는 뜯을 수가 없다. 이는 위에서 언급했듯 주어진 배열이 Circular Buffer 형태이기 때문이다. 그렇다면 다음에 뜯을 수 있는 스티커는 최소 세 번째 스티커부터 가능하다. 세번째를 바로 뜯을 지, 아니면 네번째를 뜯을 지에 따라 반환되는 누적합이 다를 것이다.
다음으로는 첫 번째 스티커를 뜯지 않고 시작한다고 생각해보자. 그렇다면 처음으로 뜯을 수 있는 스티커는 최소 두 번째 스티커부터 시작하여 앞의 결과에 따라 마지막 스티커까지 뜯을 수 있을 것이다 (첫번째 스티커를 뜯지 않으므로 마지막 스티커는 위 경우와는 다르게 더 이상 인접한 스티커가 아니다). 즉 여기서 우리는 첫 번째 스티커를 어떻게 할 건지에 따라 2개의 분기로 나뉜다는 것을 알 수 있다.
일단 점화식에 다시 집중해보자. 위에서 우리는 인접한 스티커는 연달아 뗄 수 없기 때문에 최소 1칸 이상 건너뛰어야 한다는 것을 알 수 있었다. 즉 다음의 두 가지를 생각해볼 수 있다.
그리고 1번과 2번을 실행했을 때 각각의 결과값이 있을 것이다. 우리가 필요한 것은 최댓값이기 때문에 1번과 2번 중에 최댓값을 계속 추출하면 된다. 따라서 위의 과정을 마지막까지 반복한다면 우리가 선언간 dp 배열의 마지막엔 최댓값이 들어있게 될 것이다. 말로 하면 이해가 잘 안 갈 수 있으니 바로 코드를 보자.
dp[i] = Math.max(dp[i-1], dp[i-2] + sticker[i]);
dp[i-1]
의 의미는 현재 뜯어야 할 스티커가 i번째 일 때, 이미 이전의 스티커까지 뜯었을 때의 최댓값을 의미한다. 따라서 i번째 바로 직전의 스티커를 뜯었으므로 현재 i번째 스티커는 뜯을 수가 없다. 따라서 i번째의 최댓값은 당연히 이전의 최댓값과 동일하게 될 것이다.
반면 dp[i-2]
의 경우는 한 칸 건너뛰어 그 이전의 스티커를 뜯었을때 까지의 최댓값을 의미한다. 즉 인접한 스티커가 아니기 때문에 현재 스티커 sticker[i]
를 뜯을 수 있다. 따라서 이 둘의 합이 최댓값이 될 수 있는 수가 될 것이다.
이제 다시 앞으로 돌아가서 위에서 생각한 두 가지 경우를 생각해보자. 위의 점화식만으로는 정답을 얻을 수가 없다. 왜냐하면 첫 번째 스티커는 뜯을 수도 있고, 뜯지 않을 수도 있기 때문이다. 따라서 이 조건을 고려해주어야 한다.
이를 위해 두 개의 dp 배열을 선언해주자. dp1 은 1번째 스티커를 뜯는 dp배열을 말하고, dp2는 1번째 스티커를 뜯지 않았을 때의 dp배열을 의미한다. 이때 우리가 처음에 선언해준 DP 배열을 살짝 바꿔주어야 한다. 왜냐하면 위의 점화식에서 i-2
의 값을 구해주는 것을 알 수 있다. 그런데 스티커의 크기와 동일하게 DP 배열을 만들어주면 첫 시작에 마이너스 값의 인덱스를 가리키게 되므로, 이를 막아주기 위해 sticker.length + 2
의 크기를 가진 두 개의 DP 배열을 만들어 주자.
const len = sticker.length + 2;
const dp1 = new Array(len).fill(0);
const dp2 = new Array(len).fill(0);
// 만일 스티커가 하나밖에 없다면
// 첫번째 원소가 최댓값이므로 바로 리턴해주자.
if(sticker.length === 1) return sticker[0];
두 개의 DP 배열을 만들었다면 위에서 찾은 점화식을 적용할 수 있다. 이때 각각의 배열은 첫 스티커를 뜯는 경우와 그렇지 않은 경우로 분기한다는 것에 유의하자. 또한 기존에는 sticker[i]
로 바로 현재 스티커의 값을 찾을 수 있었지만, DP 배열의 크기가 +2 되었으므로 해당 스티커 역시 sticker[i-2]
로 찾아주어야 한다.
// 첫 스티커를 뜯는 경우
// 따라서 마지막 스티커는 뜯을 수 없으므로
// len-1 까지 반복해주어야 한다.
for(let i = 2; i < len-1; i++)
dp1[i] = Math.max(dp[i-1], dp[i-2] + sticker[i-2]);
// 첫 스티커를 뜯지 않는 경우
// 따라서 마지막 스티커를 뜯을 수 있으므로
// len 까지 반복하고 i는 3부터 시작한다.
for(let i = 3; i < len; i++)
dp2[i] = Math.max(dp[i-1], dp[i-2] + sticker[i-2]);
위 과정을 모두 수행하고 나면 dp1은 마지막 스티커를 떼지 않으므로 dp1[len-2]
위치에 최댓값이 있을 것이고 dp2는 마지막 스티커를 뗄 수 있으므로 dp2[len-1]
에 최댓값이 담겨 있을 것이다. 따라서 두 값 중에 최댓값을 정답으로 리턴해주면 된다. 다음은 주석을 제외한 전체 코드이다.
코드
function solution(sticker) {
const len = sticker.length + 2;
const dp1 = new Array(len).fill(0);
const dp2 = new Array(len).fill(0);
if(sticker.length === 1) return sticker[0];
for(let i = 2; i < len-1; i++)
dp1[i] = Math.max(dp1[i-1], dp1[i-2] + sticker[i-2]);
for(let i = 3; i < len; i++)
dp2[i] = Math.max(dp2[i-1], dp2[i-2] + sticker[i-2]);
return Math.max(dp1[len-2], dp2[len-1]);
}
좋은 설명 덕분에 도움이 되었습니다 ㅎㅎ
설명이 너무 잘 되어있어서, 제 블로그에 이 글의 링크를 달고 싶은데 괜찮을까요?!