[Java] 프로그래머스(level-2) - 땅따먹기
문제 풀이
이 문제는 동적 계획법, DP 를 이용한 방법으로 적은 수의 라인으로 풀 수 있는 문제이다.
그리디? 완전탐색?
사실, 문제를 보고 그리디 알고리즘이나 완전탐색으로 접근하려 했으나 두 가지 모두 문제 통과는 어렵다고 판단하였다.
그리디 알고리즘을 적용할 경우 최선의 값을 선택하기에 좋은 솔루션으로 생각할 수도 있겠지만, 문제에서 주어지는 행에서의 최대값을 선택한다고 마지막 행까지의 덧셈을 통해 최댓값이 구해지는 것은 아니다. 아래 예시를 보자.
1
2
3
[1, 4, 3, 2]
[9, 8, 7, 6]
[10, 4, 2, 1]
위 배열을 보면 4 -> 9 -> 4 로 최대값을 선택하면서 내려왔다면 값은 17이다. 다만, 4 -> 7-> 10 이나 3 -> 8 -> 10을 선택하면서 내려왔다면 21이라는 최대값을 만들 수 있다.
여기서 알 수 있는 점은 매 행에서 최대값을 선택하는 그리디 알고리즘을 적용하는 것은 적절하지 않다는 것이다!
또한 N의 범위는 최대 100,000이기에 완전 탐색을 이용하기엔 시간초과가 걸린다.
아이디어 도출
그렇다면 행마다 한번씩 내려가면서, 최고의 합을 기록하며 내려간다면 어떻게 될까? 위에서 살펴 본 배열을 한 번더 예시로 들어보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
[1, 4, 3, 2]
[9, 8, 7, 6]
[10, 4, 2, 1]
// 두번째 행을 최고의 합으로 갱신
[1, 4, 3, 2]
[13(9+4), 11(8+3), 11(7+4), 10(6+4)]
[10, 4, 2, 1]
// 마지막 행을 최고의 합으로 갱신
[1, 4, 3, 2]
[13, 11, 11, 10]
[21(10+11), 17(4+13), 15(2+13), 14(1+13)]
위와 같이 내려오면서 land 배열의 각 자리마다 이전 행의 최대값을 더해주면서 내려온다면 마지막 행에서 21이라는 최대값을 반환하기만 된다는 것을 알 수 있다.
결국, 위와 같은 방법으로 배열의 각 자리를 갱신하면서 마지막 행에서 가장 큰 값을 가진 값을 반환하면 된다!
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;
class Solution {
int solution(int[][] land) {
int answer = 0;
int len = land.length;
/**
* 행을 한번씩 내려가면서, 내려올때의 최고의 합을 land에 기록해나간다.
*
* 배열의 2번째 행부터 현재 칸과 이전 행의 최댓값을 더한 값으로 갱신해나간다.
* 이때, 이전에 최댓값이 된 칸의 경우 같은 칸을 더하지 않도록 한다.
*/
for(int i=1; i<len; i++) {
land[i][0] += Math.max(land[i-1][1], Math.max(land[i-1][2], land[i-1][3]));
land[i][1] += Math.max(land[i-1][0], Math.max(land[i-1][2], land[i-1][3]));
land[i][2] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][3]));
land[i][3] += Math.max(land[i-1][0], Math.max(land[i-1][1], land[i-1][2]));
}
// 마지막 행 중 최대값을 구하여 반환한다.
for(int num : land[len-1]) {
answer = Math.max(answer, num);
}
return answer;
}
public static void main(String[] args) {
Solution sol = new Solution();
// int[][] land = new int[][]{{1,2,3,5},
// {5,6,7,8},
// {4,3,2,1}};
// int[][] land = new int[][]{{1,1,1,1},
// {2,2,2,3},
// {3,3,3,6},
// {4,4,4,7}};
int[][] land = new int[][]{{1,4,3,2},
{9,8,7,6},
{10,4,2,1}};
sol.solution(land);
}
}
회고
출처
- —
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.