[프로그래머스/Lv. 2] 땅따먹기 (JAVA)
📖 문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
💡 풀이 방식
• DP
1. dp 배열의 값을 초기화한다.
- 0번째 행의 값은 land 배열의 값 그대로 채운다.
2. 1 ~ (land.length - 1)행까지 dp 배열을 채운다.
- 0번째 열인 경우, 이전 행의 1,2,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][0]을 더한다.
- 1번째 열인 경우, 이전 행의 0,2,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][1]을 더한다.
- 2번째 열인 경우, 이전 행의 0,1,3열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][2]을 더한다.
- 3번째 열인 경우, 이전 행의 0,1,2열의 값 中 큰 값과 land배열에서 현재 좌표 위치에 있는 값 land[i][3]을 더한다.
3. 마지막 행에서 최댓값을 구하고 출력한다.
💥 유의사항
완전탐색으로 풀면 틀린다
🔺 코드
|
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
|
import java.util.*;
class Solution {
int solution(int[][] land) {
int answer = 0;
int len = land.length;
int[][] dp = new int[len][4];
// dp 배열 0번째 행 값 초기화
for(int i = 0 ; i < 4 ; i++) {
dp[0][i] = land[0][i];
}
// dp 배열 값 채우기 (이전 행에서 다른 3열의 값 중 가장 큰 값 찾아 현재 land 배열 칸의 값과 더하기)
for(int i = 1 ; i < len ; i++) {
dp[i][0] = getMax(dp[i - 1][1], dp[i - 1][2], dp[i - 1][3]) + land[i][0];
dp[i][1] = getMax(dp[i - 1][0], dp[i - 1][2], dp[i - 1][3]) + land[i][1];
dp[i][2] = getMax(dp[i - 1][0], dp[i - 1][1], dp[i - 1][3]) + land[i][2];
dp[i][3] = getMax(dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]) + land[i][3];
}
// 마지막 행에서 가장 큰 값 찾아 출력하기
for(int i = 0 ; i < 4 ; i++) {
answer = Math.max(answer, dp[len - 1][i]);
}
return answer;
}
// 세 값 중 가장 큰 값 구하는 메소드
private static int getMax(int a, int b, int c) {
return Math.max(Math.max(a, b), c);
}
}
|
cs |
➕ 다른 풀이 방식
- 더 간단하게는 이렇게,, dp배열 따로 만들 필요가 없었던 것이다,,
[프로그래머스] level2. 땅따먹기 (자바 JAVA)
[ 문제 ] [프로그래머스] level2. 땅따먹기 (자바 JAVA) 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)
ilmiodiario.tistory.com
- 이런 3중 for문 풀이도..!
[프로그래머스] 땅따먹기 (JAVA)
문제 출처 - Programmers 문제는 여기 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부
blackvill.tistory.com
💦 어려웠던 점
처음에 그저 완탐,, 으로 풀 생각을 하였는데 그게 아니라 DP 문제였던 것이다,,
30분 완탐해보다가 안되어서 DP로 풀어봤더니 맞았다,,,
좀 접근 방식 찾기까지 돌아오긴 했지만 그래도 혼자 풀어서 뿌듯해ㅠㅠ
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V |