[코딩테스트 합격자 되기(Java)] 문제 69. 조약돌 문제★ ★ ★

문제

3열 N행의 가중치가 있는 배열 arr이 주어집니다.

이 배열에 다음 규칙을 준수하면서 조약돌을 놓을 때 최대 가중치의 합을 반환하는 Solution() 함수를 구현하세요.

 

제약조건

• 각 열에 조약돌은 적어도 하나는 놓아야 합니다.
• 각 조약돌에 바로 인접한 위치에 조약돌을 놓을 수 없습니다.

- 인접 기준은 상하좌우입니다.

 

입출력의 예

arr	return
[ [ 1, 3, 3, 2 ], [ 2, 1, 4, 1 ], [ 1, 5, 2, 3 ] ]	19
[ [ 2, 7, 13, 2, 6 ], [ 2, -4, 2, 5, 4 ], [ 5, 3, 5, -3, 1 ] ]	32

 

 

 

---

풀이 및 코드

3열 N행에서 각 열에 조약돌을 놓는 방법은 다음과 같다.

예) 1행에서

1. 1열에 두는 방법		이전 행에서 2열이나 3열을 선택했을 때 가능 두 경우 중 가중치가 더 큰 값 선택
2. 2열에 두는 방법		이전 행에서 1열이나 3열을 선택하거나, 두 열을 동시에 선택했을 때 가능 세 경우 중 가중치가 더 큰 값 선택
3. 3열에 두는 방법		이전 행에서 1열이나 2열 선택했을 때 가능 두 경우 중 가중치가 더 큰 값 선택
4. 1열&3열에 두는 방법		이전 행에서 2열 선택했을 때 가능

 

위를 참고하여 각각 경우를 선택했을 때 가중치합을 dp 배열에 저장한다.

 

 

import java.util.Arrays;

public class Main {
    private static int solution(int[][] arr) {
        // 선택 방법은 네 가지 있음. (1열), (2열), (3열), (1열, 3열)
        int[][] dp = new int[arr[0].length][4]; // (0:1열), (1:2열), (2:3열), (3:1열,3열)
        dp[0][0] = arr[0][0];
        dp[0][1] = arr[1][0];
        dp[0][2] = arr[2][0];
        dp[0][3] = arr[0][0] + arr[2][0];

        for(int i = 1; i < arr[0].length; i++) {
            dp[i][0] = Math.max(dp[i-1][1], dp[i-1][2]) + arr[0][i]; // 1열 선택 -> 전 행에서 2열이나 3열 선택
            dp[i][1] = Math.max(Math.max(dp[i-1][0], dp[i-1][2]), dp[i-1][3]) + arr[1][i]; // 2열 선택 -> 전 행에서 1열이나 3열 선택
            dp[i][2] = Math.max(dp[i-1][0], dp[i-1][1]) + arr[2][i]; // 3열 선택 -> 전 행에서 1열이나 2열 선택
            dp[i][3] = dp[i-1][1] + arr[0][i] + arr[2][i]; // 1,3열 선택 -> 전 행에서 2열 선택
        }
        return Arrays.stream(dp[dp.length-1]).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[][] {{1, 3, 3, 2}, {2, 1, 4, 1}, {1, 5, 2, 3 }})); // 19
        System.out.println(solution(new int[][] {{1, 7, 13, 2, 6}, {2, -4, 2, 5, 4}, {5, 3, 5, -3, 1}})); // 32
    }
}