백준 17404번: RGB거리 2

백준 17404번: RGB거리 2

문제

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

N(1 $\le N \le $1,000)개의 집을 빨강, 초록, 파랑으로 칠할 때 아래의 조건을 만족시키며 가장 적은 비용을 구하는 문제이다. 각 집을 칠할 때의 비용은 1,000 이하의 자연수이다.

1번 집의 색은 2번, N번 집과 달라야 한다.

N번 집의 색은 N-1번, 1번 집과 달라야 한다.

i($1 \le $i$ \le N-1$)번 집의 색은 i-1번, i+1번 집과 달라야 한다.

풀이

우선 첫 번째 집의 색을 정한 후에 배열을 이용하여 색깔별로 가장 최소값을 찾는다.

선택하지 않은 색은 10,000,000으로 설정해 모든 집의 개수(1,000)와 비용(1,000)의 곱보다 큰 수로 설정하였다.

코드

C++

#include int min(int a, int b) {return a < b ? a : b;} int main() { int n; scanf("%d", &n;); int **cost = new int*[n]; int **dp = new int*[n]; for(int i=0; i

", answer); for(int i=0; i

Java

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { public static int min(int a, int b) {return a < b ? a : b;} public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int n = Integer.parseInt(bf.readLine()); int[][] cost = new int[n][3]; int[][] dp = new int[n][3]; for(int i=0; i

Python

import sys n = int(sys.stdin.readline()) cost = [] for _ in range(n): cost.append(list(map(int, sys.stdin.readline().split()))) dp = [[0 for _ in range(3)] for _ in range(n)] answer = float('inf') for color in range(3): for i in range(3): dp[0][i] = float('inf') if i != color else cost[0][i] for i in range(1, n): dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1]) for i in range(3): if i != color: answer = min(answer, dp[n-1][i]) print(answer)

from http://hyeonchan.tistory.com/9 by ccl(A) rewrite - 2021-09-23 06:28:21