젬니
Jemin IT블로그
젬니
전체 방문자
오늘
어제
  • 분류 전체보기 (189)
    • [Engineering] (3)
    • [PGS] (8)
    • [BOJ] (20)
    • [백엔드] (3)
    • [DevOps] (14)
    • [Django] (2)
    • [ Algorithm] (33)
    • [SqL] (12)
    • [Techit] (6)
    • [InteliJ 설정] (0)
    • [CS 공부] (42)
    • [DB] (22)
    • [TDD] (1)
    • [NCP] (4)
    • [for Rest 프로젝트] (11)
    • [Kotlin] (3)
    • [비공개 공부] (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 햣

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
젬니

Jemin IT블로그

[JAVA] 1149 RGB거리
[BOJ]

[JAVA] 1149 RGB거리

2023. 4. 14. 18:44

풀이과정

이렇게 각 집마다 색깔을 겹치지 않게 색칠해줘야 한다.

그렇다면 2,2를 파랑으로 색칠할때 이미 최소값 계산이 다 되었다고 가정한 주황색중에 작은 값을 고른다.

(색이 겹치면 안되기 때문에 [1][2]는 제외시켰다.) 

주황색중 작은 값을 파랑에 더하면  최소값이 나온다.

그렇다면 이걸 sudo코드로 바꾸자면 [2][2] += min([1][0], [1][1])이다.

맨 초반 고정값은 그대로 넣어주고 그 값을 토대로 각 배열의 최소값들을 식으로 표현한다면 사진과 같이 나온다.

맨 아래 나온 N번째 식을 점화식을 토대로 최소값을 구해준다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class backJoon1149 {
    static int[][] house;
    static int[][] dp;

    final static int Red = 0;
    final static int Green = 1;
    final static int Blue = 2;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        house = new int[N][3];
        dp = new int[N][3];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            house[i][Red] =  Integer.parseInt(st.nextToken());
            house[i][Green] =  Integer.parseInt(st.nextToken());
            house[i][Blue] =  Integer.parseInt(st.nextToken());
        }
        dp[0][Red] = house[0][Red];
        dp[0][Green] = house[0][Green];
        dp[0][Blue] = house[0][Blue];

        System.out.println(Math.min(minCost(N-1, Red), Math.min(minCost(N-1, Green), minCost(N-1, Blue))));
    }
    public static int minCost(int N, int color) {
        //아직 방문하지 않은 집 확인
        if(dp[N][color] == 0) {
            //저장한 값을 불러와 최소값 저장
            if(color == Red) {
                dp[N][Red] = Math.min(minCost(N-1, Green), minCost(N-1, Blue)) + house[N][Red];
            }
            else if(color == Green) {
                dp[N][Green] = Math.min(minCost(N-1, Red), minCost(N-1, Blue)) + house[N][Green];
            }
            else {
                dp[N][Blue] = Math.min(minCost(N-1, Red), minCost(N-1, Green)) + house[N][Blue];
            }
        }
        return dp[N][color];
    }
}

결과

dp에 저장된 최소값들도 출력해줬다. 이렇게 보면 더 이해하기 편할것이다.

'[BOJ]' 카테고리의 다른 글

[JAVA] 11725 트리의 부모 찾기  (0) 2023.05.01
[JAVA] 11726 2×n 타일링  (0) 2023.04.14
[JAVA] 21939 문제 추천 시스템 Version 1  (0) 2023.03.26
[JAVA] 11286 절대값  (0) 2023.03.23
[JAVA] 4358 생태학  (0) 2023.03.21
    '[BOJ]' 카테고리의 다른 글
    • [JAVA] 11725 트리의 부모 찾기
    • [JAVA] 11726 2×n 타일링
    • [JAVA] 21939 문제 추천 시스템 Version 1
    • [JAVA] 11286 절대값
    젬니
    젬니

    티스토리툴바