https://school.progammers.co.kr/learn/courses/30/lessons/12913#
🔊 문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총
N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때,각 행의 4칸 중 한 칸만 밟으면서내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때,같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
처음에는 각 행을 인덱스(열)와 함께 점수를 기준으로 내림차순으로 정렬한 후, 전 행에서 선택한 인덱스(열)과 겹치치 않게만 하도록 구현하였는데, 테스트만 통과하고 제출 후 채점하기에서 단 하나도 맞는게 없어서... 대체 뭐가 문제인가 싶었다..
알고보니 이것은 DP 문제였다! 각 행에서 마냥 가장 큰 점수만을 선택하게 되면 같은 열을 연속해서 밟을 수 없는 특수 규칙 때문에 최댓값을 구할 수 없게된다.
예를 하나 들어보자.
위와 같은 경우가 있다고 하자.
첫번째 줄에서 가장 큰 점수인 5를 선택하고, 두번째 줄에서 5와 겹치지 않는 점수 중 가장 큰 점수인 7을 선택하고, 3번째 줄에서 7과 겹치지 않는 3을 선택하며 내려온다고 하자. 이 때, 총 점수는 5 + 7 + 3 = 15이지만, 더 좋은 방법은 4 + 9 + 4 = 17이다.
첫번째 줄에서 가장 큰 점수인 5를 선택하게 되면, 다음 줄에 9가 같은 열에 있으므로 7을 선택하게 된다. 하지만, 이런식으로 5와 7을 선택하는 것 보다 4와 9를 선택하게 되는 것이 더 큰 점수이기 때문에 무조건 지금 상황에서의 최선을 선택하는 이와 같은 탐욕법 으로 문제를 푼다면 다음 줄에서 더 큰 숫자의 기회를 잃을 수 있는 것이다.
가장 빠른 길을 찾을때, 그리디 알고리즘(탐욕법) 에서는 전체적인 상황을 고려 하지 않고 순간순간 교차로가 보일 때 마다 가장 빠른 경로를 탐색하는 반면, DP는 우리가 갈 수 있는 모든 상황과 교통 정체를 전부 감안하여 최적의 경로를 찾아낸다고 보면 됩니다.
따라서 DP를 활용하면, 각 자리에 전 행에서 자신과 같은 열을 제외한 점수 중 가장 큰 점수를 합한 값으로 갱신해가며 최종적으로 마지막 행에서 가장 큰 값을 return 하면 된다!
✍️ 나의 최종 풀이
function solution(land) {
land.forEach((row, rowIdx) => {
row.forEach((col, colIdx) => {
let arr = row.filter((it, idx) => idx !== colIdx);
if(rowIdx < land.length - 1){
land[rowIdx + 1][colIdx] += Math.max(...arr);
}
})
})
return Math.max(...land[land.length - 1]);
}참고 문헌
https://shanepark.tistory.com/183
이 글을 통해 문제 풀이를 쉽게 이해할 수 있었다.
