728x90
풀이
"백준 1149, RGB거리"에 조건이 추가된 문제이다.
입력받은 비용들을 여러 번 사용해야 하고, 처음에 고른 색에 따라 최소비용을 계산해주어야 한다.
소스코드
#include <stdio.h>
#define MAX 1000001
#define MIN(a,b) (a < b ? a : b)
int main(){
int N, result = MAX;
scanf("%d", &N);
int cost[N][3], min[3] = {0,}, old[3] = {0,};
for (int i = 0; i < N; i++)
scanf("%d %d %d", &cost[i][0], &cost[i][1], &cost[i][2]);
for (int i = 0; i < 3; i++){
old[0] = old[1] = old[2] = MAX;
old[i] = cost[0][i];
for (int j = 1; j < N; j++){
min[0] = cost[j][0] + MIN(old[1], old[2]);
min[1] = cost[j][1] + MIN(old[0], old[2]);
min[2] = cost[j][2] + MIN(old[0], old[1]);
for (int k = 0; k < 3; k++)
old[k] = min[k];
}
for (int j = 0; j < 3; j++)
if (i != j) result = MIN(result, min[j]);
}
printf("%d\n", result);
}
출처 및 참고자료
17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
[백준 1149] RGB거리 [C]
풀이 문제의 조건은 다음과 같이 해석 가능하다. 이전에 선택한 색상(index)만 고르지 않으면 된다. (=방금 입력받은 비용 중, 이전 색상의 비용을 제외하고 남은 두 색상의 비용중에 최솟값을 선
kyr-db.tistory.com
728x90
'PS > Baekjoon Online Judge' 카테고리의 다른 글
[백준 10800] 컬러볼 [C] (0) | 2021.09.05 |
---|---|
[백준 1377] 버블 소트 [C] (0) | 2021.09.05 |
[백준 1818] 책 정리 [C] (0) | 2021.09.04 |
[백준 12738] 가장 긴 증가하는 부분 수열 3 [C] (0) | 2021.09.04 |
[백준 14003] 가장 긴 증가하는 부분 수열 5 [C] (0) | 2021.09.04 |