[Java] 백준 1149 RGB거리

Lee GaEun·2024년 11월 20일

JAVA 알고리즘 again 백준

[Java] 알고리즘

목록 보기

21/93

1149 RGB거리 문제 링크

문제분석

RGB거리에는 1번 집부터 N번 집이 순서대로 있음
모든 집을 빨강, 초록, 파랑 중 하나의 색으로 칠할 예정
각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어질 때, 모든 집을 칠하는 최소 비용 구하기

제약 사항

i (2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 함

입력 조건

첫째 줄 : 집의 수 N(2 ≤ N ≤ 1,000)
둘째 줄 : 각 집을 빨강, 초록, 파랑으로 칠하는 비용
- 비용은 1,000보다 작거나 같은 자연수

출력 조건

모든 집을 칠하는 비용의 최솟값 출력

#1


import java.util.Scanner;

class Solution
{
    static Scanner sc = new Scanner(System.in);
    static int N = sc.nextInt();
    static int[][] arr = new int[N][3];

    public static void main(String args[]) throws Exception
    {
        int answer = 9999;
        for(int i=0; i<N; i++) {
            for(int j=0; j<3; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        for(int i=0; i<3; i++) {
            int[][] result = new int[N][2];
            result[0][0] = arr[0][i];
            result[0][1] = arr[0][i];

            answer = Math.min(answer, calculate(arr, result, i, 1)); // a=0
        }

        System.out.println(answer);
        sc.close(); // 사용이 끝난 스캐너 객체를 닫습니다.
    }

    static int calculate(int[][] arr, int[][] result, int rgb, int a) { // rgb는 이전항이 몇번항인지 체크 , a는 이게 몇번째인지 체크
        if(a==N) return 0;

        int min = Integer.MAX_VALUE;
        
        for(int index=0; index<2; index++) {
            for(int i=0; i<3; i++) {
                if(rgb == i) continue;
                result[a][0] = result[a-1][0] + arr[a][i];
                result[a][1] = result[a-1][1] + arr[a][i];

                min = Math.min(min, Math.max(result[a][index], calculate(arr, result, i, a+1)));
            }
        }

        return min;
    }
}

dp로 풀려고 노력은 함
근데 결국 재귀로 모든 값을 다 구하는 거랑 다름이 없음..
이건 dp가 아니라 dfs임..
~~이걸거면 값을 왜 저장했는데..~~

#2


import java.util.Scanner;

class Solution
{
    static Scanner sc = new Scanner(System.in);
    static int N = sc.nextInt();
    static int[][] arr = new int[N][3];

    public static void main(String args[]) throws Exception
    {
        int answer = 9999;
        for(int i=0; i<N; i++) {
            for(int j=0; j<3; j++) {
                arr[i][j] = sc.nextInt();
            }
        }

        for(int i=0; i<3; i++) {
            answer = Math.min(answer, calculate(i, 1, arr[0][i]));
        }

        System.out.println(answer);
        sc.close(); // 사용이 끝난 스캐너 객체를 닫습니다.
    }

    static int calculate(int prevColor, int visit, int currentCost) {
        if(visit==N) return currentCost;

        int minCost = Integer.MAX_VALUE;

        for(int i=0; i<3; i++) {
            if(prevColor == i) continue;
            minCost = Math.min(minCost, calculate(i, visit+1, currentCost+arr[visit][i]));
        }

        return minCost;
    }
}

시간 복잡도가 높아서 런타임에러가 발생하는 건가 싶어서
일단 깔끔하게 정리함
필요없는 거 삭제하고 그냥 값으로 바로바로 재귀 돌림

#3

import java.util.Scanner;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] cost = new int[N][3];
        int[][] dp = new int[N][3];

        // 입력값 읽기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 3; j++) {
                cost[i][j] = sc.nextInt();
            }
        }

        // 초기값 설정
        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

        // DP 계산
        for (int i = 1; i < N; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
            dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
        }

        // 결과값 계산
        int answer = Math.min(dp[N - 1][0], Math.min(dp[N - 1][1], dp[N - 1][2]));
        System.out.println(answer);

        sc.close(); // Scanner 닫기
    }
}