프로그래머스 - 땅따먹기

 

<문제>

https://school.programmers.co.kr/learn/courses/30/lessons/12913?language=javascript

프로그래머스

 

<문제 핵심>

1. 탐색 알고리즘을 사용해야하나 고민했는데 결론은 동적 계획법을 사용하여 누적된 최대값을 구하는 문제였다. 즉, 각 행의 칸마다 그 이전 행의 최대값을 이용해 결과를 축적하는 방식으로 문제를 풀어야한다. 시간 복잡도는 동적 계획법을 사용하기 때문에 O(n)이 나온다.

 

결국 land 배열 중 마지막 요소에서 가장 큰 값을 출력하면 된다.(누적 되어 있을거니까)

-> [4, 3, 2, 1] 배열

land 배열

 

2. 각 행마다 같은 열은 제외해야 한다는 점 또한 문제에서 요구하는 핵심 포인트였다.

 

단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

 

<문제 풀이과정 및 순서도>

 

1. 1행부터 시작하여 이전 행(i-1)에서 지금 현재 행(i)이랑 다른 인덱스의 값들의 최대값을 구하여 현재 행의 각 자리에 더한다. 

 

2. 마지막 요소에서 가장 큰 값을 고르면 된다.( 각 행에는 이전의 모든 행들의 최댓값이 누적되어 있음)

 

<전체 코드>

function solution(land) {
    let answer = 0;
    //O(n)으로 사용
    for(let i = 1; i < land.length; i++) {
        land[i][0] += Math.max(land[i-1][1],land[i-1][2],land[i-1][3])
        land[i][1] += Math.max(land[i-1][0],land[i-1][2],land[i-1][3])
        land[i][2] += Math.max(land[i-1][0],land[i-1][1],land[i-1][3])
        land[i][3] += Math.max(land[i-1][0],land[i-1][1],land[i-1][2])
    }
    
    answer = land[land.length-1]//land의 마지막 요소
    
    return Math.max(...answer);
}

 

 

해당 코드는 reduce를 사용하는 방법으로 다른 분의 코드를 참고해보았다. ...가 reduce의 반환 결과를 풀어서 Math.max에 넘기는 방식이다.

function solution(land) {
    return Math.max(
        ...land.reduce((a,c) => {
            return [
                c[0] + Math.max(a[1], a[2], a[3]),
                c[1] + Math.max(a[0], a[2], a[3]),
                c[2] + Math.max(a[0], a[1], a[3]),
                c[3] + Math.max(a[0], a[1], a[2]),
            ]
        })
    )
}