오늘 풀어본 문제는 프로그래머스의 땅따먹기라는 문제이다.
문제 설명은 다음과 같다.
문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
제한사항
- 행의 개수 N : 100,000 이하의 자연수
- 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
- 점수 : 100 이하의 자연수
위 문제는 아래로 내려가면서 땅에 숫자를 더해가며 가장 큰 숫자를 만드는 문제이다.
문제에서 한 가지 규칙기 있는데 그것은 현재 땅 바로 아래에 있는 땅은 밟지 못한다는 것이다.
문제를 보고 처음에 든 생각은 탐욕법을 적용하여 푸는 방법이었다.
현재 행에서 가장 큰 수를 고르면서 바로 아래 땅이 가장 큰 수면 그 다음으로 큰 수를 밟게 하는 풀이를 생각해 보았다.
하지만 이 풀이는 현재 땅의 가장 큰 수 다음 바로 밑의 수가 가장 큰 수이고 현재 땅에서 두번째로 큰 수와 이 수가 더해졌을 때 현재 땅의 가장 큰 수와 다음 땅의 두번째 큰 수를 더한 값보다 클 때 문제가 생긴다.
그래서 다른 풀이를 생각해 보았다.
다음으로 생각한 풀이는 메모이제이션을 이용한 풀이이다.
가장 아래에서 시작해서 위에 수를 더해주며 더해준 값이 가장 큰 수만 남기는 방법이다.
이 방법을 적용하여 풀었더니 정답을 받을 수 있었다.
문제 풀이 코드는 다음과 같다.
import java.util.*;
class Solution {
int solution(int[][] land) {
int answer = 0;
int[][] table = new int[land.length][land[0].length];
table[land.length - 1] = land[land.length - 1];
for (int i = land.length - 1; i > 0; i--) {
for (int j = 0; j < land[i].length; j++) {
for (int k = 0; k < land[i].length; k++) {
if (j != k) {
table[i - 1][k] = Math.max(table[i - 1][k], table[i][j] + land[i - 1][k]);
}
}
}
}
for (int i = 0; i < table[0].length; i++) {
if (answer < table[0][i]) {
answer = table[0][i];
}
}
return answer;
}
}우선 땅 배열인 land와 같은 크기의 table 변수를 생성해준다.
그리고 table의 가장 밑에 값을 원래 땅의 가장 아래 값들로 넣어준다.
반복문 안에서는 가장 아래에서 시작하여 위까지 반복하며 땅을 두개씩 비교하여 현재땅 바로 위를 제외하고 더한 값과 원래 존재하던 값을 비교하여 더 큰 값을 넣어준다.
이렇게 반복하게 되면 가장 위에 남은 값은 더한 값 중 가장 큰 값들로만 남게 되고 맨 위에서 가장 큰 수를 찾게 되면 정답을 받을 수 있게 된다.
