접근
처음에는 각 행에서 제일 큰 값만 취한다면 결국 제일 큰 값이 나올 것이다.
라고 생각했지만 이전 행에서 선택한 열은 이번 행에서 선택은 못하기 때문에 예외 사항이 생길 수 있다.
예를 들어
[ [1,2,3,4],
[3,4,5,9], ] 다음과 같은 입력이 주어지고 각 행에서 제일 큰 값을 선택 한다고 했을 때 첫 번째 행에서 제일 큰 값 4를 선택하고 아래 행에서 같은 열인 9는 선택 못하고 그 다음 큰 값인 5를 선택해 9가 된다.
하지만 첫 번째 행에서 3을 선택하고 다음행에서 9를 선택한다면 최종값이 12가 된다.
따라서 다른 방법을 써야한다.
두 번째로 완전탐색을 생각해보았다.
구할 수 있는 모든 경우의 수에서 최종값이 가장 크다면 그게 정답일 것이다.
하지만 해당 문제의 N의 최대값은 100,000이다.
모든 경우의 수를 구한다면 열의 개수가 4이니 4x(4-1)x(4-1)x....x(4-1) 을 N번해야 하는데 어림잡아 3의 N제곱이 될 것이다. 왜냐하면 첫 번째 행에서 모든 열을 선택할 수 있으니 4이고 그 다음 행부터는 이전 행에서 선택한 열을 선택못하니 4-1의 가짓수가 남는다.
근데 3의 N제곱은 너무 크다... 이 방법으로는 이번 문제를 풀 수 없다.
마지막 방법은 참고해서 풀었는데 DP로 풀면 된다.
작은 문제의 정답이 모이면 큰 문제의 정답으로 향하기 때문에
이전 행에서 가장 큰 값을 해당 행에서 전부 더해주고 같은 열에 있는 값은 이전 행에서 두 번째로 큰 값을 더해준다. 그렇게 되면 해당 행에서 구할 수 있는 최대값이 나온다.
예를 들어
[ [1,2,3,4],
[3,4,5,9], ] 에서 2번째 행을 위의 말대로 진행해주면
[ [1,2,3,4],
[7,8,9,12], ]가 된다.
function solution(land) {
var answer = 0;
for(let low=1; low<land.length; low++){
let [ oneIdx , twoIdx ] = findLargestTwoVal(land[low-1]);
for(let col=0; col<4; col++){
if(oneIdx == col) continue;
land[low][col]+=land[low-1][oneIdx];
}
land[low][oneIdx] += land[low-1][twoIdx];
}
answer = Math.max(...land[land.length-1]);
return answer;
}
function findLargestTwoVal(arr){
let tempArr = [...arr];
let idxOfFirst = findFisrtLargestVal(tempArr);
let idxOfSecond = findFisrtLargestVal(tempArr);
return [idxOfFirst, idxOfSecond];
}
function findFisrtLargestVal(arr){
let idx = 0;
for(let i=1; i<arr.length; i++){
if(arr[idx] < arr[i] ) idx = i;
}
arr[idx] = -1;
return idx;
}
후기
이번 문제 구현에서 어려웠던 점이 두 번째로 큰 값을 구하는 방법이었다.
첫 번째 값은 array를 돌면서 이전 값과 비교해 큰 값을 기록하며 찾으면 된다.
하지만 두 번째 값은 여러 방법이 있다.
array에 중복된 값이 없다고 가정한다면 array [1,2,3,4,5]에서 가장 큰 값은 5이고 이 값을 기준으로 5보다 작지만 이전 값 보다 큰 값을 넣어주면 된다.
하지만 array의 값이 중복될 수 있다면? [5,5,1,2,4]라면 생각해야할 부분이 많아진다. 내 기준에서 중복이 생길 때 안생길 때 전부 예외사항이 몇개 생겨났는데 이를 해결하기 위해 단순하게 가장 큰 값을 해당 array에서 가장 작은 값(-1)으로 만들었다. 그렇게 되면 두 번째로 큰 값이 가장 큰 값이 되어 찾기가 수월해진다.
ex) [5,5,1,2,4]를 처음 순회할 때 가장 큰 값은 5이고 해당 값을 -1로 치환 [-1,5,1,2,4] 다시 배열을 순회하면 두 번째로 큰 값을 쉽게 찾을 수 있다.
