[프로그래머스] 땅따먹기

이번 문제는 DP(동적 프로그래밍) 문제라는데 전 솔직히 책을 읽어봐도 동적 프로그래밍이 뭔 소리인지 잘 모르겠습니다...

느낌적으로 동적 프로그래밍이라는 게 기존 테이블에다가 특정 식을 적용한 다른 값을 기존 테이블에 담아 최솟값과 최댓값을 구하는 것 같은데 잘 이해가 안 됩니다.

 

이 코드가 제 코드가 아니라 풀었다고 하기가 좀 그렇네요.😥

 

---

그래도 동적 프로그래밍이 뭔지에 대해 설명하겠습니다.

 

동적 프로그래밍(dynamic programming)

• 문제의 크기가 작은 소문제에 대한 해를 저장해 놓고 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 상향식 접근 방법
• 최솟값 또는 최댓값을 구하는 최적화 문제에 주로 사용
• 최적성의 원리
  • 주어진 문제에 대한 최적해가 소문제에 대한 최적해로 구성된다는 원리
• 동적 프로그래밍의 적용 단계
  1. 주어진 문제에 대해서 최적해를 제공하는 점화식 도출
  2. 가장 작은 소문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장
  3. 테이블에 저장되어 있는 소문제의 해를 이용하여 점차적으로 큰 상위 문제의 해를 구함

 

동적 프로그래밍에는

• 피보나치 수열문제
• 연쇄 행렬 곱셈 문제
• 스트링 편집 거리 문제
• 모든 정점 간의 최단 경로
• 저울 문제

가 있습니다.

---

접근 방법

이 문제의 조건 중에서 "같은 열을 연속해서 밟을 수 없는 특수 규칙"이 있습니다.

이 말 때문에 진짜 애를 먹는 문제입니다.

 

생각해보면 "같은 열을 연속해서 밟을 수 없는 특수 규칙" 이 말은

내가 밟고 있는 다음 칸에 대해 생각하면 됩니다.

다다음, 처음부터 끝까지 다 생각하면서 코드를 짤 필요가 없다는 말입니다.

 

물론 제가 생각한 방법은 아니지만 사람들이 한 방식은 표로 설명하자면

• 왼쪽은 땅따먹기 기존 land 2차원 배열입니다.
• 오른쪽은 코드를 적용했을 때의 바뀐 land 2차원 배열입니다.

1	2	3	5	→	1	2	3	5
5	6	7	8		5+5 10	6+5 11	7+5 12	8+3 11
4	3	2	1		4+12 16	3+12 15	2+11 13	1+12 13

현재 행의 land값에 이전 행의 land값에서 같은 위치 빼고 그중에서 가장 큰 수를 더해 주었습니다.

이 말을 코드로 짜주고 마지막에 마지막 행에서 가장 큰수를 추출해주면 됩니다.

---

해결방안

function solution(land) {
    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])
    }
    
    return Math.max(...land[land.length-1])
}

 

 

• for문을 i=1 시작한 이유는 아래 표를 보시면 알겠지만 land[0][]은 바뀌지 않고 그대로 사용하기 때문에 1부터 시작하였습니다.

land[i][0]	land[i][1]	land[i][2]	land[i][3]
1	2	3	5
(2, 3, 5 중에서 5가 가장 큼) 5+5 10	(1, 3, 5중에서 5가 가장 큼) 6+5 11	(1, 2, 5중에서 5가 가장 큼) 7+5 12	(1, 2, 3중에서 3이 가장 큼) 8+3 11
(11, 12, 11중에서 12가 가장 큼) 4+12 16	(10, 12, 11중에서 12가 가장 큼) 3+12 15	(10, 11, 11중에서 11가 가장 큼) 2+11 13	(10, 12, 11중에서 12가 가장 큼) 1+12 13

나머지 코드는 위에 표를 보시면 이해하실 수 있을 거라고 생각합니다.

---

여기까지 프로그래머스 땅따먹기 구하기 해결방안에 대해 설명해보았습니다.