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

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

문제

설명

n행 4열의 점수가 적혀있는 땅이 주어진다

1행부터 한행씩 내려오면서 4열 중 하나만 밟으면서 내려와야 한다

같은 열은 다음 행에서 또 밟을 수 없다

나올 수 있는 최댓값을 반환

예시 필드

예로 이런 땅이 있다면

100 -> 9 -> 100 = 209 (x) ( 2행과 3행의 위치가 같아서 안됨)

100 -> 1 -> 100 = 201 (o) ( 각 행의 위치가 다 다름)

이런식이다

import java.util.*;
/*
 * 프로그래머스 땅따먹기
 * 땅은 n행 4열, 모든 칸에는 점수가 있음
 * 1행부터 한행씩 내려오면서 4칸 중 하나만 밟으면서 내려와야 함
 * 같은 열 또 밟을 수 없다
 * 나올 수 있는 최댓값 반환
 */
class Solution {
    int solution(int[][] land) {
        for (int i = 0; i < land.length - 1; i++) {
            // 각 열의 최댓값, 두번째 최댓값, 최댓값의 자리
            int max1 = -1;
            int max2 = -1;
            int idx1 = -1;

            for (int j = 0; j < 4; j++) {
                int tmp = land[i][j];

                if (tmp > max1) { // 새로운 1등 발견
                    max2 = max1; // 기존 1등이 2등으로 밀림
                    max1 = tmp;
                    idx1 = j; // 자리 기록
                } else if (tmp > max2) { // 1등보다 작고, 2등보다 큰 경우
                    max2 = tmp;
                }
            }

            // 다음 열에 더해주기
            for (int j = 0; j < 4; j++) {
                // 같은 자리가 아니라면 최댓값
                // 같은 자리라면 두번째 최댓값 더해주기
                if (j != idx1) {
                    land[i + 1][j] += max1;
                } else {
                    land[i + 1][j] += max2;
                }
            }
        }

        return Arrays.stream(land[land.length - 1]).max().getAsInt();
    }
}

그래서 각 행마다 최댓값과 두번째 최댓값 그리고 최댓값의 자리를 구해서

다음 행의 각 열마다 최댓값을 더해주었다

 

만약 전 행의 최댓값과 같은 열이라면 구해두었던 두번째 최댓값을 더해주었다

반환은 마지막 행의 최댓값을 반환해주어 마무리해주었다

 

요즘 DP 문제를 몇개 풀었더니 DP식으로 문제를 풀려고 하는거 같다

나름 재밌는 문제였음

https://github.com/qTeTp/Algo/tree/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/2/12913.%E2%80%85%EB%95%85%EB%94%B0%EB%A8%B9%EA%B8%B0

Algo/프로그래머스/2/12913. 땅따먹기 at main · qTeTp/Algo