Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- DFS
- 자바
- 코딩테스트준비
- 그리디
- lower bound
- 백트래킹
- 우선순위큐
- DP
- 브루트포스
- BFS
- 정렬
- BinarySearch
- Til
- 그래프 이론
- 백준
- 완전탐색
- 트리
- 네트워크 계층
- 그래프
- 스프링
- 데이터베이스
- Spring
- 스프링 핵심 원리 - 기본편
- 99클럽
- 알고리즘
- 프로그래머스
- 항해99
- 동적 프로그래밍
- Java
- 개발자취업
Archives
- Today
- Total
AtraFelis's Develop Diary
[백준] 1149 - RGB거리 (C언어) 본문
SIVLER I
문제
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)
번 집의 색은i-1
번,i+1
번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
풀이
문제를 보자마자 동적 프로그래밍을 처음으로 배웠을 때 풀었던 문제인 돌놓기
가 생각났다. 그 문제와는 고려해야할 조건이 조금 다르지만, 실질적으로 거의 같은 문제라고 볼 수 있다.
26 40 83
49 60 57
13 89 99
문제에서 입력이 이렇게 주어졌다면, 초기 dp
배열에는 26 40 83
만 들어간다.
이후 두 번째부터가 중요한데, 각각 49 60 57
을 선택했을 때, 얻을 수 있는 최솟값을 구하여 dp
와 원래 배열과 같은 위치에 값을 삽입하면 된다. 예를 들어, 49
일 때는, 40
과 83
중 40
이 더 작으므로 40
을 선택하여 66
이라는 값을 넣으면 된다. 그러므로, dp[1]
에는 89 86 83
이 들어간다.
이 과정을 n번 반복해서 dp[n-1]
까지 가득 채운 후, dp[n-1]
의 원소 중 최솟값이 이 문제의 해가 된다.
전체 코드
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int rgb[1000][3];
int dp[1000][3];
for (int i = 0; i < n; i++)
scanf("%d %d %d", &rgb[i][0], &rgb[i][1], &rgb[i][2]);
dp[0][0] = rgb[0][0];
dp[0][1] = rgb[0][1];
dp[0][2] = rgb[0][2];
for (int i = 1; i < n; i++) {
for (int k = 0; k < 3; k++)
{
int tmp = dp[i-1][(k+1)%3] < dp[i-1][(k+2)%3] ? dp[i-1][(k+1)%3] : dp[i-1][(k+2)%3];
dp[i][k] = tmp + rgb[i][k];
}
}
int answer = dp[n-1][0] < dp[n-1][1] ? dp[n-1][0] : dp[n-1][1];
answer = answer < dp[n-1][2] ? answer : dp[n-1][2];
printf("%d", answer);
return 0;
}
'Algorithm > 백준' 카테고리의 다른 글
[백준] 10815 - 숫자 카드 (JAVA) (0) | 2024.12.30 |
---|---|
[백준] 1389 - 케빈 베이컨의 6단계 법칙 (C언어) (0) | 2024.07.10 |
[백준] 1005 - ACM Craft (JAVA) (0) | 2024.06.24 |
[백준] 12865 - 평범한 배낭 (JAVA) (0) | 2024.05.21 |
[백준] 16953 - A → B (JAVA) (0) | 2024.05.14 |