[프로그래머스] 땅따먹기 (LV2 - JavaScript)

프로그래머스

1. 문제

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

 

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

2. 정답 풀이

풀이 전략

• 연산 횟수를 줄이기 위해 DFS(깊이 우선 탐색) 대신 이전 상태를 이용하는 DP(동적 프로그래밍) 방식 사용

function solution(land) {
    // 첫 번째 행은 이미 정해진 값이므로, 두 번째 행(인덱스 1)부터 순회
    for (let i = 1; i < land.length; i++) {
        // 현재 행의 모든 열 순회
        for (let j = 0; j < land[0].length; j++) {
            // 이전 행을 복사
            let prev = [...land[i-1]];
            // 같은 열을 연속으로 밟을 수 없기 때문에 해당 값을 0으로 설정
            prev[j] = 0;
            // 현재 칸에 이전 행에서 밟을 수 있는 최댓값을 더함
            land[i][j] += Math.max(...prev);
        }
    }

    // 최종적으로 마지막 행에서 가장 큰 값을 반환 (모든 경로 중 최댓값)
    return Math.max(...land[land.length - 1]);
}

 

 

 

처음에는 모든 경로를 탐색하며 최댓값을 찾는 방식(DFS)으로 접근하려 했지만, 입력으로 큰 배열이 들어왔을 때를 생각해 보니 시간 복잡도가 증가해 효율적인 계산이 어려워 보였습니다.

그래서 동적 프로그래밍으로 접근을 바꿨습니다. DP를 사용하면 이전 행의 결과를 활용해 중복 계산을 피할 수 있었습니다. 이를 통해 시간 복잡도를 크게 줄이고, 문제를 효율적으로 해결할 수 있었습니다.

 

이번 문제를 통해 DP의 중요성을 느끼는 기회가 되었습니다. DP는 많이 다뤄보지 않아서 관련된 문제들 많이 찾아봐야겠습니다..🤔🤔

 

 

[프로그래머스] 뒤에 있는 큰 수 찾기 (LV2 - JavaScript)

 

[프로그래머스] k진수에서 소수 개수 구하기 (LV2 - JavaScript)