Notice
Recent Posts
Recent Comments
Link
«   2024/03   »
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
Archives
Today
Total
관리 메뉴

차근차근

[백준 1149] RGB거리 본문

대학교/Algorithm

[백준 1149] RGB거리

SWKo 2020. 2. 13. 13:44

0. 제목

  • 백준 1149 RGB거리
  • BOJ 1149 RGB거리
  • C++ 1149 RGB거리

1. 문제

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


2. 풀이

  • 이웃끼리는 같은 색을 칠할 수 없다.
  • RGB를 각각 0번, 1번, 2번 색이라 하겠다.
  • 0번색을 칠하면 이웃집은 1, 2가 가능하고 1번색을 칠하면 이웃집은 0, 2가 가능하고 2번색을 칠하면 이웃집은 0, 1이 가능하다.
  • arr[i][j]은 i번째 집에 j번 색으로 칠하는 비용이다.
  • dp배열의 초기값으로 첫번째 집의 비용을 설정해주었다.
  • 그 다음부터 dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0] 와 비슷한 방식으로 1이면 0,2, 2이면 0,1로 설정하여 실행하였다.
  • 그렇게 마지막 N번째 loop까지 다 돌고 난 후 N번째에 세가지 색중에 하나로 칠한 각각의 최소비용이 나온다.
  • 그 세 개중 최솟값이 모든 집을 칠하는 비용의 최솟값이 된다.

3. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
 
int N;
int arr[1001][3];
int dp[1001][3];
 
int main(int argc, const char * argv[]) {
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> arr[i][0>> arr[i][1>> arr[i][2];
    
    dp[1][0= arr[1][0];
    dp[1][1= arr[1][1];
    dp[1][2= arr[1][2];
    for(int i = 2; i <= N; i++){
        dp[i][0= min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
        dp[i][1= min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
        dp[i][2= min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
    }
    cout << min(min(dp[N][0], dp[N][1]), dp[N][2]) << '\n';
    return 0;
}
 
 

'대학교 > Algorithm' 카테고리의 다른 글

[백준 2170] 선 긋기  (0) 2020.02.15
[백준 1699] 제곱수의 합  (0) 2020.02.15
[백준 11650] 좌표 정렬하기  (0) 2020.02.13
[백준 2751] 수 정렬하기 2  (0) 2020.02.13
[백준 2667] 단지번호붙이기  (0) 2020.02.13
Comments