peacekim
할 수 있는 것과 할 수 없는 것.
peacekim
전체 방문자
오늘
어제
  • 분류 전체보기 (68)
    • 👨‍🏫ps (44)
      • ❄️프로그래머스 (20)
      • 🔟0️⃣백준 (21)
      • leetcode (3)
    • ✍🏻study (20)
      • 👐java (6)
      • 🍃spring (1)
      • 🥇algorithm (0)
      • 🚘oodp (4)
      • 📒 jpa (3)
      • 👣DB (2)
      • 🌂네트워크 (0)
      • 🎸기타 (3)
      • 👊 kotlin (1)
      • 🫥 jvm (0)
    • 📽project (4)
      • 🎀ReBoN (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

인기 글

최근 글

티스토리

hELLO · Designed By 정상우.
peacekim
👨‍🏫ps/🔟0️⃣백준

[백준] 17404번 RGB거리 2 풀어보기 [Java]

[백준] 17404번 RGB거리 2 풀어보기 [Java]
👨‍🏫ps/🔟0️⃣백준

[백준] 17404번 RGB거리 2 풀어보기 [Java]

2022. 3. 2. 15:54
반응형

모든 집을 가장 적은 비용으로 색칠하는 문제이다.

조건으로는

  • 현재 집에서 바로 전 집과 다음 집에는 다른 색을 칠해야 된다.
  • 처음과 끝 집은 이어져 있다.

 

👨‍🏫 풀이

DP문제이다. 처음 집과 마지막 집을 제외하고는 이전 집의 색깔만 다르게 칠하면 조건을 만족할 수 있다.

 

1. 집을 색칠하기 시작할 때, 처음 집의 색깔을 정해놓고 칠한다.

2. 지금 칠하는 색과 다른 색으로 칠한 앞에 집의 값중에서 작은 것을 선택한다.

 

 

첫번째 집은 항상 미리 선택을 해놓기 때문에, 두번째 집만 첫번째 집의 색을 선택한 값으로 설정을 해놓는다. 첫번째 집과 동일한 색을 칠하는 경우는 MAX_VALUE로 설정을 해준다.

 

return 값은 첫번째 집과 마지막 집이 같으면 안되기 때문에, 다른 색으로 칠해진 값중 작은 값을 return 해준다.

 

👨🏻‍💻코드

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

public class Main {
    static int N;
    static int[][] cache, cost;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        cost = new int[N][3];
        cache = new int[N][3];
        for(int i = 0 ; i < N ; i++){
            cost[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(n -> Integer.parseInt(n)).toArray();
        }

        int ans = Integer.MAX_VALUE;
        ans = Math.min(ans, dp(0));
        ans = Math.min(ans, dp(1));
        ans = Math.min(ans, dp(2));

        System.out.println(ans);
    }
    static int dp(int s){
        cache[0][0] = cost[0][0];
        cache[0][1] = cost[0][1];
        cache[0][2] = cost[0][2];

        int notS1 = (s+1) % 3;
        int notS2 = (s+2) % 3;

        //다음꺼는 s를 선택하면 안됨
        cache[1][s] = Integer.MAX_VALUE;
        cache[1][notS1] = cache[0][s] + cost[1][notS1];
        cache[1][notS2] = cache[0][s] + cost[1][notS2];

        for(int i = 2 ; i < N ; i++){
            cache[i][0] = Math.min(cache[i-1][1], cache[i-1][2]) + cost[i][0];
            cache[i][1] = Math.min(cache[i-1][0], cache[i-1][2]) + cost[i][1];
            cache[i][2] = Math.min(cache[i-1][0], cache[i-1][1]) + cost[i][2];

        }

        return Math.min(cache[N-1][notS1], cache[N-1][notS2]);
    }

}
반응형

'👨‍🏫ps > 🔟0️⃣백준' 카테고리의 다른 글

[백준] 11724번 연결 요소의 개수 풀어보기 [백준]  (0) 2022.03.04
[백준] 15661번 링크와 스타트 풀어보기 [Java]  (0) 2022.03.04
[백준] 1759번 암호 만들기 풀어보기 [Java]  (0) 2022.03.04
[백준] 1748번 수 이어 쓰기 1 [Java]  (0) 2022.03.02
[백준] 13398번 연속합 2 [Java]  (0) 2022.03.02
    '👨‍🏫ps/🔟0️⃣백준' 카테고리의 다른 글
    • [백준] 15661번 링크와 스타트 풀어보기 [Java]
    • [백준] 1759번 암호 만들기 풀어보기 [Java]
    • [백준] 1748번 수 이어 쓰기 1 [Java]
    • [백준] 13398번 연속합 2 [Java]
    peacekim
    peacekim
    할 수 있는 것과 할 수 없는 것. github: https://github.com/PyeongGangKim

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.