서론 :
프로그래머스의 땅 따먹기 문제를 풀던 도중 감이 잡히지 않아
정답을 찾고자 다른 이들의 풀이를 보려고 했습니다.
그러나 많은 블로그들은 DP 알고리즘을 통해 문제를 풀어야 한다고 적어 두기만 하고
자세한 설명이나 알고리즘 풀이가 아닌 똑같은 정답 코드들만
복사 붙여 넣기 되어있었습니다.
정답 코드만 붙여 넣어 풀 수도 있겠지만 그러면 의미가 없을 것 같아서
DP알고리즘 개념 공부를 먼저 진행하고 난 다음 제가 직접 풀어 보기로 했습니다.
사실 저는 프로그래머스 땅따먹기 문제를 풀면서 DP 알고리즘을 처음 접해보았습니다.
다른 이들이 복붙 했던 똑같은 정답 코드들이 훨씬 더 효율적이더라도 직접 문제를 풀었다는 것에 만족하겠습니다.
물론 정답 코드를 참고하고 개선점을 찾는 과정도 필요하여 정답 코드는 문제를 다 푼 후에 확인 해보았습니다.
본론 :
DP 알고리즘의 설명은 아래 영상을 보고 이해했습니다
만약 DP 알고리즘을 모르신다면 아래 영상을 꼭 봐주세요
https://www.youtube.com/watch?v=0bqfTzpWySY
영상에서 보았듯이 저도 기억하기 알고리즘이 좀더 와 닿아서 기억하기 알고리즘이라고 개념을 잡아갔습니다.
DP 알고리즘 개념이 어느 정도 잡혔다고 생각하고 문제 풀이 해보겠습니다.
풀 문제는 프로그래머스의 땅 따먹기 문제입니다.
프로그래머스 땅 따먹기 : https://school.programmers.co.kr/learn/courses/30/lessons/12913
영상을 통해 메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여 수행 속도를 개선한다고 배웠습니다.
그래서 똑같은 자료구조를 하나 만들고 진행하겠습니다.
테스트 케이스는
프로그래머스 질문하기에 있었던 반례를 참고했습니다.
Int[][] land = new int[][]{{6,7,1,2}, {2,3,10,8}, {1,3,9,4}, {7,11,4,9}})}
먼저 첫번째라인은 연산을 할 필요가 없기 때문에 그대로 복사만 해줍니다.
새롭게 생성한 newLand라는 메모리에 각각의 최대값을 구하고 값을 저장해보겠습니다.
강조된 칸의 데이터를 구하려면 먼저 2와 먼저 저장해두었던 [0][x] 의 값을들 더해주면서 가장 큰 값을 더해주면 됩니다.
여기서 주의해야할 점은 문제의 조건처럼 같은 열인 경우는 해당 안되니 6은 안됩니다.
무슨 뜻인지는 그림을 보면서 이해하시면 더 편합니다.
사진과 같은 과정을 진행하면 가장 큰 수는 9가 될테니 9를 해당 칸에 저장해둡니다.
다음 과정도 같습니다.
중간 과정은 생략하겠습니다. 계속 진행 하면
DP newLandTable은 아래와 같이 나옵니다
그럼 맨 마지막 열의 가장 큰 수를 반환 해주면 됩니다.
이제 코드로 풀어보겠습니다.
package Question;
import java.util.Arrays;
import java.util.Stack;
public class LandEat {
public static void main(String[] args) {
System.out.println(solutionDP(new int[][]{{1,2,3,5},{5,6,7,8},{4,3,2,1}}));
System.out.println(solutionDP(new int[][]{{4,7,8,3},{2,4,7,5},{3,1,2,6}}));
System.out.println(solutionDP(new int[][]{{9,8,7,6},{9,8,7,6},{7,9,7,6}}));
System.out.println(solutionDP(new int[][]{{4,3,2,1},{1,2,3,4},{4,3,2,5}}));
System.out.println(solutionDP(new int[][]{{1,2,3,4},{1,2,3,4},{1,2,4,3}}));
System.out.println(solutionDP(new int[][]{{6,7,1,2}, {2,3,10,8}, {1,3,9,4}, {7,11,4,9}}));
System.out.println(solutionDP(new int[][]{{6,7,1,2}, {2,3,10,8}, {1,3,9,4}, {7,11,4,9}}));
}
/**
* DP 알고리즘 구현
* 풀이 방향의 도움을 받았음.
*
* */
static int solutionDP(int[][] land) {
int[][] newLand = new int[land.length][4]; // DP를 위한 메모리
// 첫번째 줄,열 값 넣어주기, 초기화
for (int i = 0; i < land[0].length; i++) {
newLand[0][i] = land[0][i];
}
/**
* 다음줄의 DP를 사용할 때, 자기와 같은 열은 제외함.
* 첫번째 열은 이미 돌았으니 1부터 시작
*/
for (int i = 1; i < land.length; i++) {
for (int j = 0; j < land[i].length; j++) {
int max = 0;
for (int k = 0; k < 4; k++) {
if(j != k && max < (land[i][j] + newLand[i-1][k])){
max = land[i][j] + newLand[i-1][k];
}
}
newLand[i][j] = max;
}
}
int resultMax = 0;
for (int i = 0; i < newLand[newLand.length-1].length; i++) {
if(resultMax < newLand[newLand.length-1][i]){
resultMax = newLand[newLand.length-1][i];
}
}
return resultMax;
}
}
풀이는 이렇습니다. 먼저 구하려는 칸의 전 행 [i-1] 로 돌아가 같은 열을 제외한 나머지를 3번 다 더해보고 가장 큰 값을 넣어주면 됩니다. 이걸 반복해서 위와 같은 결과를 만든 후에
마지막열에서 가장 큰 값을 반환해주면 됩니다.
그렇게 하면 모든 경우의 수를 안따져도 가장 큰값을 구할 수 있습니다.
