[프로그래머스] Lv2. 땅따먹기 - dp

알고리즘을 그래도 꾸준히 풀었다고 생각했는데 하반기 코테 탈락이 많았다.

뭐가 문제일까. 왜 꾸준히 풀었다고 생각했지만 실력이 늘었다는 느낌이 없을까 고민해보니 문제가 몇 가지 있었다.

 

1. 시간을 정하지 않고 푼다.

고민 시간을 정해놓지 않으니 집중해서 풀이법을 생각해내지 않고 그렇다고 끝까지 붙잡아서 풀어내는 것이 아니라 설렁설렁 고민하다가 구글링으로 풀이를 보고 넘어간다. 이게 가장 큰 문제였다. 생각하는 힘을 키워야 한다. 연습이든 실전이든 1시간 안에 접근법 조차 생각하지 못하면 그건 틀린 문제다.

1시간을 잡고 그 안에 접근법을 생각해내자.

 

2. 유형을 공부하지 않았다.

dp, 이분탐색, 다익스트라...등등 알고리즘 유형을 공부하고 문제를 반복해서 풀기 힘들어 유형을 외면하고 그저 문제를 보고 생각 나는대로 주로 완전탐색, 그래프 탐색 위주로 문제를 풀어왔다. 힘들고 귀찮지만,,,열심히 유형별로 훈련해야한다.

이를 위해 앞으로 잠시 멈췄던 알고리즘 포스팅을 꾸준히 해보려 한다.

풀이를 정리해서 포스팅하며 내것으로 만드는 과정을 꾸준히 하다보면 저절로 유형 공부가 되지 않을까 싶다.

그리하야 오늘의 포스팅 문제..!!

프로그래머스 레벨 2. 땅따먹기

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

문제를 요약하면

1. n행 4열의 땅을 한 행씩 밟아 내려간다. 

2. 각 땅에는 점수가 적혀 있다. 

3. 같은 열을 연속해서 밟을 수 없다. 

4. 마지막 행까지 내려왔을 때 얻을 수 있는 최대값을 리턴하라. 

 

이전에 어떤 값을 선택하느냐에 따라 다음 행의 선택 값이 달라진다.

이전값 중 최대값을 선택하여 현재 행의 값과 더한다는 과정이 모두 동일하다. 

-> dp

 

dp는 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘이다. 

 

dp 풀이방법 

1. 테이블 정의하기

2. 점화식 찾기

3. 초기값 정하기

 

1. 테이블 정의하기 

d[i][j]=i행 j열의 최대 점수

 

2. 점화식 찾기

land[i][0]=land[i][0]+max(land[i-1][1],land[i-1][2],land[i-1][3])

land[i][1]=land[i][1]+Math.max(land[i-1][0],land[i-1][2],land[i-1][3])
land[i][2]=land[i][2]+Math.max(land[i-1][0],land[i-1][1],land[i-1][3])

land[i][3]=land[i][3]+Math.max(land[i-1][0],land[i-1][1],land[i-1][2])

 

본인이 속한 열을 제외한 나머지 열들의 이전 행 점수 중에 최대값을 구해 현재의 행의 점수와 더함. 

 

3. 초기값

위의 문제에선 점화식을 land 자체의 값을 덮어씌우는 형태로 세워서 초기값 또한 자동으로 land[0][0],land[0][1],land[0][2],land[0][3]을 사용하게 된다. 

 

풀이

function solution(land) {
    let n=land.length
    for(let i=1;i<n;i++){
        land[i][0]=land[i][0]+Math.max(land[i-1][1],land[i-1][2],land[i-1][3])
        land[i][1]=land[i][1]+Math.max(land[i-1][0],land[i-1][2],land[i-1][3])
        land[i][2]=land[i][2]+Math.max(land[i-1][0],land[i-1][1],land[i-1][3])
        land[i][3]=land[i][3]+Math.max(land[i-1][0],land[i-1][1],land[i-1][2])
    }
    return (Math.max(...land[n-1]))  
}