백준 1149 자바 - RGB거리

백준 1149 자바 - RGB거리

728x90

문제

https://www.acmicpc.net/problem/1149

문제해결

- dp 배열에 n번째 집을 각 색으로 칠하는데 최소값을 집어 넣는다

- 연속된 색을 칠하면 안되니 1일때는 2,3의 최소값 2일때는 1,3의 최소값... 이런식으로 같은 색은 제외한다

- dp[n] 에서 가장 작은 수가 답인데, 이때 나올수 있는 수중 가장 큰 값인 1000*1000으로 min을 초기화해서 가장 작은 수를 구한다

import java.util.Scanner; public class B1149 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] dp = new int[n+1][4]; for (int i = 1; i <= n; i++) { for (int j = 1; j < 4; j++) { dp[i][j] = sc.nextInt(); } } for (int i = 2; i <= n; i++) { dp[i][1] += Math.min(dp[i-1][2], dp[i-1][3]); dp[i][2] += Math.min(dp[i-1][1], dp[i-1][3]); dp[i][3] += Math.min(dp[i-1][1], dp[i-1][2]); } int min = 1000*1000; for (int i = 1; i < 4; i++) { min = Math.min(min, dp[n][i]); } System.out.println(min); } }

728x90

from http://broship.tistory.com/243 by ccl(A) rewrite - 2021-09-06 08:01:38