[Java] 백준 1149 RGB거리

1149 RGB거리 문제 링크

문제 분석

• 집을 빨강, 파랑, 초록 중 하나로 칠하는 비용이 각각 주어짐
• ( i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 함 )
• 다음을 만족하는 최솟값을 구하는 문제

입력 조건

• 첫째 줄 : 집의 수 N(2 ≤ N ≤ 1,000)
• 둘째 줄 : 각 집을 빨강, 초록, 파랑으로 칠하는 비용 (1번 집부터)

출력 조건

• 최솟값 출력

---

#1

• 해당 값을 2차원 배열로 만들기
• 집 개수만큼 반복
  • 열마다 최솟값 구하기
  • 다 더하기
• 출력

import java.util.*;

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

        int z = a.nextInt();
        int[][] b = new int[z][z];
        for(int i=0; i<z; i++){
            for(int j=0; j<z; j++){
                b[i][j] = a.nextInt();
            }
        }

        int answer = 0;
        for(int i=0; i<z; i++){
            int min1 = 0;
            int min2 = 1000;
            for(int j=0; j<z-1; j++){
                min1 = Math.min(b[j][i], b[j+1][i]);
                min2 = Math.min(min1, min2);
            }
            answer += min2;
        }

        System.out.println(answer);
    }
}

하다보니 이렇게 하면 안된다는 걸 깨달았다
각 열에 하나씩만 되는게 아니라 이웃한 집이랑만 색이 다르면 된다는 것..
애초에 열도 3개씩밖에 없음... 😵

---

#2

• 해당 행의 최솟값(a)과 위치(ai)를 구하기
• 집 개수만큼 반복
  • 다음 행의 최솟값(b)과 위치(bi)를 구하기
  • 만약 위치가 같고 a가 b보다 크다면 (ai==bi && a>b)
  • 아니면 answer에 a 더하고 a에 b값 넣기

*엥.. 근데 그럼 세 번째 집때문에 두 번째 집의 색이 바뀌면 첫 번째 집의 색도 최솟값의 색으로 다시 바뀌어야 되는 거 아닌가..?*

---

아이디어가 떠오르지 않아서 블로그를 참고했다..
참고 블로그

확실히 누적값으로 하면 될 것 같다.. 똑똑한 사람들..

---

• 집의 개수만큼 반복
  • nR += 누적 값(n)
  • nG += 누적 값(n)
  • nB += 누적 값(n)
• 가장 작은 값 출력