1번 2번 3번 .. n번 집을 인접한 집의 색과는 다르게 칠했을 경우
최소비용 값을 구하는 문제

ex. ) 1번집이 빨강 파랑 초록 중 빨강을 선택했다면 2번쨰 집은 빨강이 아닌 파랑 초록 중에 골라야 하고 3번째 집은 2번째 집에 의존하여 2번째 집이 칠하지 않는 색을 칠해야 한다.

3
26 40 83
49 60 57
13 89 99

먼저 해당 배열에 집을 칠하는 비용을 넣고나서
보니 배열의 특성상 0번째 부터 들어가는 것을 알고 인덱스를 1칸 더 추가해주는 것은 자유인것 같다.

0번쨰 집은 아무 색이나 먼저 칠하고 그다음으로 2번째 그다음으로 3번째가 연관이 되므로
dp[0][0]=26;
dp[0][1]=40;
dp[0][2]=83;

i행을 1부터 루프문을 출발하였다. 즉 i는 집의 번호 순으로 1행은 2번째 집이다. 이미 0행에 (1번집에) 색을 다 넣어주었다. 그리고 나서 인덱스가 1행인 (2번째 집)에서 시작하여 2번째 집의 색깔을 칠할때 그 전의 1번째 집의 칠하는 색에 의존하므로 다음과 같은 식이 도출된다.

  • i는 1부터 .

dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+arr[i][0](처음 입력받은 배열)

이말은 i+1번째 집은 이 전 집과는 다른색으로 칠해야 하므로 arr[i][0] (초기 입력 받은 배열) i+1번째 집은 빨강으로 칠하고 그 전 집은 빨강은 제외한 초록,파랑 중에 가장 작은 값을 고르게 한 것이다. 그래서 i행을 1부터 루프문으로 출발한 이유이다.

아래 코드를 보면 i번째 집이 초록색으로 칠할 경우와 i번째 집이 파랑색으로 칠할 경우 의 식이 포함되어 있다.

package oneDay_twoSol.RealTimeSolving;

import java.util.Arrays;
import java.util.Scanner;

public class RGB {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int house[][]=new int[n][3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                house[i][j]=sc.nextInt();
            }
        }
        int d[][]=new int[n][3];
        for (int i = 0; i <3 ; i++) {
            d[0][i]=house[0][i];
        }

        for(int i=1;i<n;i++){
            d[i][0] = Math.min(d[i-1][1], d[i-1][2]) + house[i][0];
            d[i][1] = Math.min(d[i-1][0], d[i-1][2]) + house[i][1];
            d[i][2] = Math.min(d[i-1][0], d[i-1][1]) + house[i][2];
        }
        for (int i = 0; i < n; i++) {
            System.out.println(  Arrays.toString(d[i]));
        }
        System.out.println(Math.min(Math.min(d[n-1][0],d[n-1][1]),d[n-1][2]));

    }
}
profile
Record then ㄱ

0개의 댓글