반응형
https://www.acmicpc.net/problem/17404
17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
[ 문제풀이 ]
https://rudalsd.tistory.com/12
[ 백준 ] 1149번 - RGB거리 (C++)
https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주..
rudalsd.tistory.com
위 글을 먼저 보고 오는 것을 추천드립니다!!
일반 RGB거리와 다른 점은 1번 집과 N번 집도 색깔이 같으면 안 된다는 조건입니다.
따라서 일반적인 RGB거리의 답을 구하는 방식으로 구하되 마지막에 1번 집과 N번 집이 같지 않을 때의 최솟값을 구하면 되는 문제입니다.
[ 소스 코드 ]
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | #define MAX 987654321 #include <iostream> using namespace std; int N; int arr[3][1001]; //각 색의 가격을 저장할 배열 int dp[3][1001]; //각 색을 칠했을 때의 총 가격 int main() { cin >> N; int ans = MAX; for (int i = 1; i <= N; i++) { cin >> arr[0][i] >> arr[1][i] >> arr[2][i]; } for (int i = 0; i < 3; i++) //첫 집의 색깔을 졍해주기 { for (int j = 0; j < 3; j++) { if (i == j) dp[j][1] = arr[j][1]; //첫 집의 색만 가격 입력 else dp[j][1] = MAX; //나머지 색은 가격 MAX } //다음 집에서 첫 집의 색을 고르지 못하도록 하기 위해서 for (int j = 2; j <= N; j++) { dp[0][j] = min(dp[1][j - 1], dp[2][j - 1]) + arr[0][j]; //앞의 집의 색 중 가격이 싼 색의 값과 지금 집 색의 값을 더함 dp[1][j] = min(dp[0][j - 1], dp[2][j - 1]) + arr[1][j]; dp[2][j] = min(dp[0][j - 1], dp[1][j - 1]) + arr[2][j]; } for (int j = 0; j < 3; j++) { if (i != j) { //마지막 집이 첫 집과 색이 같으면 안되기 때문에 i!=j 조건 넣기 ans = min(ans, dp[j][N]); } } } cout << ans; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 9328번 - 열쇠 (C++) (0) | 2022.06.20 |
|---|---|
| [ 백준 ] 1167번 - 트리의 지름 (C++) (0) | 2022.06.19 |
| [ 백준 ] 7662번 - 이중 우선순위 큐 (C++) (0) | 2022.06.17 |
| [ 백준 ] 1967번 - 트리의 지름 (C++) (0) | 2022.06.16 |
| [ 백준 ] 13549번 - 숨바꼭질 3 (C++) (0) | 2022.06.15 |