[백준] 17404

ZEDY·2024년 8월 7일

[코딩테스트] 알고리즘 문제풀이

목록 보기

38/46

백준 17404번 문제 풀이 및 디버깅 경험

문제 설명

백준 17404번 문제는 RGB 거리 2 문제로, 각 집을 RGB 색으로 칠하는데 인접한 집이 같은 색이 되지 않도록 하는 동시에 첫 번째 집과 마지막 집이 같은 색이 되지 않도록 하는 문제입니다. 목표는 모든 집을 칠하는 데 드는 최소 비용을 구하는 것입니다.

문제 해결 접근 방법

이 문제를 해결하기 위해 동적 프로그래밍(DP) 접근법을 사용했습니다. 이 방법은 다음과 같습니다:

DP 배열 정의: rgb[i][j]는 i번째 집을 j 색으로 칠하는 최소 비용을 의미합니다.
초기화: 첫 번째 집을 빨강, 초록, 파랑으로 각각 칠하는 경우를 따로 고려합니다.
이전 집과의 관계: i번째 집을 j 색으로 칠하는 비용은 이전 집을 다른 색으로 칠한 최소 비용에 현재 집을 j 색으로 칠하는 비용을 더한 값입니다.
결과 도출: 첫 번째 집과 마지막 집이 같은 색이 되지 않도록 각 경우를 분리하여 계산한 후 최소값을 구합니다.

코드 구현

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

public class P17404 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[][] numbers = new int[n+1][3];
        int[][] rgb = new int[n+1][3]; // 비용, 전에꺼 색깔

        for(int i = 1; i < n+1; i++){
            String[] line = br.readLine().split(" "); // "1 2 3 4"
            numbers[i][0] = Integer.parseInt(line[0]);
            numbers[i][1] = Integer.parseInt(line[1]);
            numbers[i][2] = Integer.parseInt(line[2]);
        } // 1~n

        int answer = Integer.MAX_VALUE;

        // 빨강으로 시작하는 경우
        rgb[1][0] = numbers[1][0];
        rgb[1][1] = 1000 * 1000;
        rgb[1][2] = 1000 * 1000;

        for(int i = 2; i <= n; i++){
            rgb[i][0] = Math.min(rgb[i-1][1], rgb[i-1][2]) + numbers[i][0];
            rgb[i][1] = Math.min(rgb[i-1][0], rgb[i-1][2]) + numbers[i][1];
            rgb[i][2] = Math.min(rgb[i-1][0], rgb[i-1][1]) + numbers[i][2];
        }
        answer = Math.min(answer, Math.min(rgb[n][1], rgb[n][2]));

        // 초록으로 시작하는 경우
        rgb[1][1] = numbers[1][1];
        rgb[1][0] = 1000 * 1000;
        rgb[1][2] = 1000 * 1000;

        for(int i = 2; i <= n; i++){
            rgb[i][0] = Math.min(rgb[i-1][1], rgb[i-1][2]) + numbers[i][0];
            rgb[i][1] = Math.min(rgb[i-1][0], rgb[i-1][2]) + numbers[i][1];
            rgb[i][2] = Math.min(rgb[i-1][0], rgb[i-1][1]) + numbers[i][2];
        }
        answer = Math.min(answer, Math.min(rgb[n][0], rgb[n][2]));

        // 파랑으로 시작하는 경우
        rgb[1][2] = numbers[1][2];
        rgb[1][0] = 1000 * 1000;
        rgb[1][1] = 1000 * 1000;

        for(int i = 2; i <= n; i++){
            rgb[i][0] = Math.min(rgb[i-1][1], rgb[i-1][2]) + numbers[i][0];
            rgb[i][1] = Math.min(rgb[i-1][0], rgb[i-1][2]) + numbers[i][1];
            rgb[i][2] = Math.min(rgb[i-1][0], rgb[i-1][1]) + numbers[i][2];
        }
        answer = Math.min(answer, Math.min(rgb[n][0], rgb[n][1]));

        System.out.println(answer);
    }
}

디버깅 경험

초기에는 rgb 배열을 초기화할 때 Integer.MAX_VALUE를 사용했습니다. 하지만 이로 인해 계산 도중 overflow가 발생하여 잘못된 결과가 나왔습니다. Integer.MAX_VALUE는 2147483647로 매우 큰 값이지만, 덧셈 연산을 반복하면 쉽게 overflow가 발생할 수 있습니다.

이를 방지하기 위해 초기 값을 1000 * 1000으로 설정하여 overflow를 피할 수 있었습니다. 이 값은 문제의 입력 값이 최대 1000 이하라는 점에서 유효합니다. 이렇게 변경한 후 문제를 올바르게 해결할 수 있었습니다.