반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식



앞이 어떻게 됐건 신경쓰지말고 i번째라고 생각해보자.


i번째 집에 r이 칠해질 때 최소 비용(DP[i][0])은 i-1번째 집에 g가 칠해져있을 때 혹은 b가 칠해져있을 때 가능하다.

i번째 집에 g가 칠해질 때 최소 비용(DP[i][1])은 i-1번째 집에 r이 칠해져있을 때 혹은 b가 칠해져있을 때 가능하다.

i번째 집에 b가 칠해질 때 최소 비용(DP[i][2])은 i-1번째 집에 r이 칠해져있을 때 혹은 g가 칠해져있을 때 가능하다.


    for (int i = 1; i < n; i++)
    {
        DP[i][0= min(DP[i - 1][1], DP[i - 1][2]) + cost[i][0];
        DP[i][1= min(DP[i - 1][0], DP[i - 1][2]) + cost[i][1];
        DP[i][2= min(DP[i - 1][0], DP[i - 1][1]) + cost[i][2];
    }


이 코드를 통해 모든 이웃간에 중복없이 집에 색칠이 조건에 맞게 칠해진다.



소스 코드 : 


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
42
43
44
#include <iostream>
#include <cstdio>
 
#define min(a,b)(a < b ? a : b)
 
using namespace std;
 
long long int cost[1001][3];
long long int DP[1001][3];
 
int main()
{
    int n;
    long long int r, g, b;
    
    scanf("%d"&n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%lld %lld %lld"&r, &g, &b);
 
        cost[i][0= r;
        cost[i][1= g;
        cost[i][2= b;
    }
 
    DP[0][0= cost[0][0];
    DP[0][1= cost[0][1];
    DP[0][2= cost[0][2];
 
    for (int i = 1; i < n; i++)
    {
        DP[i][0= min(DP[i - 1][1], DP[i - 1][2]) + cost[i][0];
        DP[i][1= min(DP[i - 1][0], DP[i - 1][2]) + cost[i][1];
        DP[i][2= min(DP[i - 1][0], DP[i - 1][1]) + cost[i][2];
    }
 
    printf("%lld", min(min(DP[n - 1][0], DP[n - 1][1]), DP[n - 1][2]));
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

'Applied > 알고리즘 문제풀이' 카테고리의 다른 글

[2042번] 구간 합 구하기  (0) 2017.03.08
[2251번] 물통  (0) 2017.03.06
[2644번] 촌수계산  (0) 2017.03.06
[11052번] 붕어빵 판매하기  (0) 2017.03.06
[1699번] 제곱수의 합  (0) 2017.03.06