[C언어] 백준 1149번 RGB거리

2025. 3. 9. 13:53· 백준
목차
  1. 문제
  2. 입력
  3. 출력
  4. 예제 입력 1
  5. 예제 출력 1
  6. 예제 입력 2
  7. 예제 출력 2
  8. 예제 입력 3
  9. 예제 출력 3
  10. 예제 입력 4
  11. 예제 출력 4
  12. 예제 입력 5
  13. 예제 출력 5
  14. 아이디어 스케치
  15. 전체 코드
  16. 제출 결과
반응형

링크

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

 

 

 

 

문제


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보다 작거나 같은 자연수이다.

 

 

 

출력


첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

 

 

 

예제 입력 1


3
26 40 83
49 60 57
13 89 99

 

 

 

예제 출력 1


96

 

 

 

예제 입력 2


3
1 100 100
100 1 100
100 100 1

 

 

 

예제 출력 2


3

 

 

 

예제 입력 3


3
1 100 100
100 100 100
1 100 100

 

 

 

예제 출력 3


102

 

 

 

예제 입력 4


6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

 

 

 

예제 출력 4


208

 

 

 

예제 입력 5


8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19

 

 

 

예제 출력 5


253

 

 

 

 

아이디어 스케치


  • 문제에서 주어진 3가지 조건을 만족하면서 시간초과가 발생하지 않게 모든 집을 칠하는 비용의 최솟값을 구하기 위해서는 동적계획법 알고리즘을 사용해야 한다.
  • i번째 집을 기준으로 색을 칠하는 경우의 수를 살펴보면
    • i번째 집이 0번색인 경우에는 i-1번째 집의 색은 1번 or 2번이 가능하다.
    • i번째 집이 1번색인 경우에는 i-1번째 집의 색은 0번 or 2번이 가능하다.
    • i번째 집이 2번색인 경우에는 i-1번째 집의 색은 0번 or 1번이 가능하다.
  • 위 3가지 경우 중 가장 작은 값을 가지는 경우가 i번째 집까지 구한 비용의 최솟값이다.
  • 위에서 구한 로직을 코드로 작성하면 문제를 해결할 수 있다.

 

 

 

 

전체 코드


#include <stdio.h>
#define min(a,b) a > b ? b : a

int dp[1001][3];

int main() {
	int n;
	int ans;

	scanf("%d", &n);	// 집의 개수를 입력 받음

	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			scanf("%d", &dp[i][j]);		//각 집마다 색깔별로 드는 비용을 입력 받음

	for (int i = 1; i < n; i++) {
		dp[i][0] += min(dp[i - 1][1], dp[i - 1][2]);	// i번째 집을 0번색으로 칠하는 경우(i-1번째 집의 색은 1번색 or 2번색을 선택해야 함)
		dp[i][1] += min(dp[i - 1][0], dp[i - 1][2]);	// i번째 집을 1번색으로 칠하는 경우(i-1번째 집의 색은 0번색 or 2번색을 선택해야 함)
		dp[i][2] += min(dp[i - 1][0], dp[i - 1][1]);	// i번째 집을 2번색으로 칠하는 경우(i-1번째 집의 색은 0번색 or 1번색을 선택해야 함)
	}

	ans = min(dp[n - 1][0], (min(dp[n - 1][1], dp[n - 1][2])));		// 3가지 경우 중 가장 작은 값을 결과값으로 저장

	printf("%d", ans);		// 결과 출력

	return 0;
}

 

 

 

 

제출 결과


 

 

 

 

 

 

반응형
LIST

'백준' 카테고리의 다른 글

[C언어] 백준 11722번 가장 긴 감소하는 부분 수열  (0) 2025.03.09
[C언어] 백준 1991번 트리 순회  (0) 2025.03.09
[C언어] 백준 15657번 N과 M (8)  (0) 2025.03.09
[C언어] 백준 15654번 N과 M (5)  (0) 2025.03.09
[C언어] 백준 1012번 유기농 배추  (0) 2025.03.09
  1. 문제
  2. 입력
  3. 출력
  4. 예제 입력 1
  5. 예제 출력 1
  6. 예제 입력 2
  7. 예제 출력 2
  8. 예제 입력 3
  9. 예제 출력 3
  10. 예제 입력 4
  11. 예제 출력 4
  12. 예제 입력 5
  13. 예제 출력 5
  14. 아이디어 스케치
  15. 전체 코드
  16. 제출 결과
'백준' 카테고리의 다른 글
  • [C언어] 백준 11722번 가장 긴 감소하는 부분 수열
  • [C언어] 백준 1991번 트리 순회
  • [C언어] 백준 15657번 N과 M (8)
  • [C언어] 백준 15654번 N과 M (5)
Woong's
Woong's
공부하다가 자꾸 까먹어서 정리해두는 블로그입니다.
인공지눙공부하다가 자꾸 까먹어서 정리해두는 블로그입니다.
Woong's
인공지눙
Woong's
전체
오늘
어제
  • 분류 전체보기 (64)
    • 논문 구현 (1)
    • 백준 (49)
    • 데이터 분석 (7)
    • 논문 리뷰 (3)
    • 머신러닝 (1)
    • Computer Vision (1)
    • 코딩테스트 (1)
    • 시계열 데이터 분석 (1)

블로그 메뉴

    인기 글

    태그

    • 백트래킹
    • transformer
    • 누적합
    • 12865번
    • C
    • 알고리즘
    • 데이터 분석
    • 트랜스포머
    • 분할정복
    • 12865
    • 데이터 전처리
    • 정렬
    • 특성 공학
    • 데이터 사이언스
    • attention is all you need
    • 동적계획법
    • 머신러닝
    • Feature Engineering
    • 백준
    • c언어

    최근 글

    hELLO · Designed By 정상우.v4.2.2
    Woong's
    [C언어] 백준 1149번 RGB거리
    상단으로

    티스토리툴바

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.