파이문

1149. RGB 거리 본문

문제 풀이/BOJ

1149. RGB 거리

민Z 2017. 4. 4. 22:41
728x90

1149. RGB 거리

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



dp[i][j]라는 배열을 만들어서, i는 i번째 집이고 j는 색을 의미하게 하였다. 그 값으로는 i번째 집이 j의 색을 가질 때, 가질 수 있는 최소 값을 넣었다. 


정리하자면 i번째 집을 j색으로 칠할 때 + (i-1번째 집이 j색이 아닌 다른색으로 칠했던 경우의 최소 값) 인 것이다.

public void problem1149(int houseCount, ArrayList<Integer> n) { int[][] dp = new int[houseCount][3]; dp[0][0] = n.get(0); dp[0][1] = n.get(1); dp[0][2] = n.get(2); for (int i=1; i<houseCount; i++) { dp[i][0] = n.get(i*3) + Math.min(dp[i-1][1], dp[i-1][2]); dp[i][1] = n.get(i*3+1) + Math.min(dp[i-1][0], dp[i-1][2]); dp[i][2] = n.get(i*3+2) + Math.min(dp[i-1][1], dp[i-1][0]); } System.out.println(Math.min(dp[h-1][0], Math.min(dp[h-1][1], dp[h-1][2])));

}


'문제 풀이 > BOJ' 카테고리의 다른 글

11053. 가장 긴 증가하는 부분 수열  (0) 2017.11.12
2579. 계단 오르기  (0) 2017.11.12
1463. 1로 만들기  (0) 2017.04.03
1003. 피보나치 함수  (0) 2017.04.03
Maximum Random Walks  (0) 2016.04.17
Comments