출처: https://www.acmicpc.net/problem/17404


문제 설명

1~N개의 집 칠하는데, 옆집과는 다른 색으로 칠하는데 필요한 최소 비용. 집의 배치는 원형으로 생각해서 첫집과 마지막집이 이웃이 되도록 한다.


입력 설명

집의 수와 각각의 집을 칠하는데 필요한 비용

출력 설명

필요한 최소 비용 


입력 예

3
26 40 83
49 60 57
13 89 99

출력 예

110

제약조건

  • 1<= N <= 1000
  • 1 <= a_i <= 1000

문제 풀이 내용

RGB거리 문제에서 약간의 변형이 있다. 집들의 시작과 끝이 연결되어 한번의 계산으로 결정할 수 없는 문제로 변형됐다. 기본 아이디어는 초기조건과 거기에 따른 제한 조건을 만족하는 최소의 값들을 찾어서, 비교하도록 했다.

첫집을 특정한 색으로 칠하는 경우에 그 색을 제외한 다른 색들은 아주 큰값으로 설정해서 다음번 집 계산에서 선택되지 않도록 해서 마지막 집까지 최소값을 구한다. 마지막집을 칠하는 최소값에서 첫집과 같은 색깔로 칠하는 경우는 배제하고 최소값을 구한다.  

프로그램 내용

더보기
/// https://www.acmicpc.net/problem/17404

/// N <= 1000
/// r_cost, g_cost, b_cost <= 1000

#include <bits/stdc++.h>

using namespace std;

const int INF = 987654321;
int tN;

int minPaint(vector<tuple<int, int, int>>& p_cost, int color)
{
    vector<tuple<int, int, int>> DP(tN+1);
     int r, g, b;

	if(color == 0) 
	{
		tie (r,g,b) = p_cost[0];
		DP[0] = make_tuple(r, INF, INF);
	}
	else if(color == 1) 
	{
		tie (r,g,b) = p_cost[0];
		DP[0] = make_tuple(INF, g, INF);
	}
	else 
	{
		tie (r,g,b) = p_cost[0];
		DP[0] = make_tuple(INF, INF, b);
	}

    for(int id=1; id < tN; ++id)
    {
        int r_c, g_c, b_c;
        tie(r_c, g_c, b_c) = p_cost[id];

        int r_p, g_p, b_p;
        tie(r_p, g_p, b_p) = DP[id-1];

        int r_n, g_n, b_n;
        r_n = r_c + min(g_p, b_p);
        g_n = g_c + min(r_p, b_p);
        b_n = b_c + min(r_p, g_p);
        DP[id] = make_tuple(r_n, g_n, b_n);
    }

	int m_paint=INF;
	if(color == 0) 
	{
		tie (r,g,b) =  DP[tN-1];
		m_paint = min(g, b);
	}
	else if(color == 1) 
	{
		tie (r,g,b) =  DP[tN-1];
 		m_paint = min(r, b);
	}
    else 
	{
		tie (r,g,b) =  DP[tN-1];
		m_paint = min(r, g);
	}
    
    return m_paint;
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> tN;

    vector<tuple<int, int, int>> p_cost(tN);

    for(int id=0; id< tN; ++id)
    {
        int r, g, b;
        cin >> r >> g >> b;
        p_cost[id] = make_tuple(r, g, b);
    }

    int cost_r = minPaint(p_cost, 0); // first hosuse red
    int cost_g = minPaint(p_cost, 1); // first hosuse green
    int cost_b = minPaint(p_cost, 2); // first hosuse blue

  int cost = min({cost_r, cost_g, cost_b}); 

    cout << cost << "\n";

    return 0;
}

 

관련 문제

 

RGB 거리 : https://www.acmicpc.net/problem/1149

'Training > Baekjoon Online Judge' 카테고리의 다른 글

BOJ 17404 - RGB거리 2  (0) 2019.12.10

출처: https://cses.fi/problemset/task/1637


문제 설명

You are given an integer n. On each step, you may subtract from it any one-digit number that appears in it.

How many steps are required to make the number equal to 0?

입력 양식

The only input line has an integer n.

입력 예

27

출력 양식

Print one integer: the minimum number of steps.

출력 예

5

Explanation: An optimal solution is 272018109027→20→18→10→9→0.

제약조건

  • 1 n 10^6

문제 풀이 내용

어떤 수의 자리수 중에서 가장 큰 숫자를 찾아서, 그 숫자들을 계속 빼주는 것이 최적의 방법이다.  어떤 수의 최적의 경우의 수는 각 자리의 수를 빼서 나온 수의 경우의 수 +1 중에서 가장 작은 것이 된다. 

입력 N 의 크기를 생각해보면, 기록할 필요 없이 가장 큰 자리수를 찾아서 빼내고, 다시 재귀적으로 돌려도 충분할 것 같다.

프로그램 내용

 

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int nNum;
    cin >> nNum;

    vector<int> DP(nNum+1, 1e9);

    DP[0] = 0;
    for (int idx=1; idx <= nNum; ++idx)
    {
        int tmp = idx;
        while(tmp)
        {
            int r_digit = tmp % 10;
            DP[idx] = min( DP[idx], DP[idx-r_digit] + 1);
            tmp /= 10;
        }
    }

    cout << DP[nNum] << "\n";

    return 0;
}

Dynamic Programming link )

'Training > CSES' 카테고리의 다른 글

CSES 3-5 Removing Digits  (0) 2019.10.14
CSES 3-4 Coin Combinations II  (0) 2019.10.10
CSES 3-3 Coin Combinations I  (0) 2019.10.09
CSES 3-2 Minimizing Coins  (0) 2019.10.09
CSES 3. Dynamic Programming  (0) 2019.10.09
CSES 2-22 Subarray Divisibility  (0) 2019.10.09

처음 풀이 ( link )


문제 풀이 내용

자물쇠 숫자 3개를 tuple<int, int, int>로 처리하고, 숫자 사이의 차이를 abs 이용해서 계산한다. 다만, modulo 연산에서 -를 지원하지 않기 때문에 dial number - 2 ( modulo -2) 보다 큰 경우도 고려한다. 3중 루프를 O(N^3)이지만 최대 dial number 100 을 생각하면, 속도에 문제가 될 것 같지는 않다. 필요하다면, key number 에서 5x5x5 로 가능한 숫자 배열을 작성하고, 그 배열 숫자들로만 루프를 돌리면 좀 더 빨라질 것 같다. 중복 제거를 위해서 set 에 무조건 입력하고, 중복이 제거된 결과의 수만 조회 했는데, 입력하기 전에 조회를 하고 없으면 입력하도록 하는것도 방법이 될 수는 있을 것 같다. 효율성은 find를 하고 없으면 입력하는것이 조금은 더 좋을 것 같다.

프로그램 내용

/*
PROB: combo
LANG: C++
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX_DIAL 100

bool check_distance(tuple <int, int, int> key, tuple <int, int, int> dest, int dial_num)
{
    int a, b, c;
    int x, y, z;
    tie(a,b,c) = key;
    tie(x,y,z) = dest;
    int dist1, dist2, dist3;

    dist1 = abs(a-x);
    dist2 = abs(b-y);
    dist3 = abs(c-z);

    if ((dist1 <= 2 || dist1 >= dial_num-2)
        && (dist2 <= 2 || dist2 >= dial_num-2)
        && (dist3 <= 2 || dist3 >= dial_num-2) )
    {
        return true;
    }
    else
        return false;
}

int main() {
    ifstream fin ("combo.in");
    ofstream fout ("combo.out");

    /// Read requirement
    int dial_num = 0;
    fin >> dial_num;

    int f1, f2, f3;
    fin>> f1 >> f2 >> f3;

    int m1, m2, m3;
    fin>> m1 >> m2 >> m3;

    set <tuple<int,int,int>> c_codes;

    tuple <int, int, int> f_key = make_tuple(f1, f2, f3);
    tuple <int, int, int> m_key = make_tuple(m1, m2, m3);

    for(int id1=0;id1 < dial_num ; ++id1)
        for (int id2 = 0; id2 < dial_num; ++id2)
            for(int id3= 0; id3 < dial_num; ++id3)
            {
                tuple <int, int, int> c_key = make_tuple(id1, id2, id3);
                /// check distance 1d1 with f1/m1, id2 with f2/m2, id3 with f3/m3
                if(check_distance(f_key, c_key, dial_num))
                    c_codes.insert(c_key);
                if(check_distance(m_key, c_key, dial_num))
                    c_codes.insert(c_key);
            }

    if (dial_num < 6)
        fout << dial_num * dial_num * dial_num << endl;
    else
        fout << c_codes.size() << endl;

    return 0;
}

 

 

Chapter 1. Getting started (link)

'Training > USACO Training' 카테고리의 다른 글

Problem 1.4.6 Combination Lock - 2  (0) 2019.10.13
Problem 1.5.3 Mother's Milk  (0) 2019.10.12
Problem 2.3.4 Money Systems  (0) 2019.10.11
Problem 2.2.4 Subset Sums  (0) 2019.10.10
Problem 2.1.5 Sorting A Three-Valued Sequence  (0) 2019.09.18
Problem 2.1.4 Ordered Fractions  (0) 2019.09.18

+ Recent posts