백준 20950번 미술가 미미

🔒[문제 url]

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

🪄전체 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int paint[31][3];
int gom[3]; // 곰두리색
int perm[31]; // 섞을 물감의 조합
int moon[3]; // 문두리색

int ans = 2e9;

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < 3; j++)
            cin >> paint[i][j];
    for(int i = 0; i < 3; i++)
        cin >> gom[i];
}

void setMoon(int size)
{// 섞을 물감의 조합(perm)을 확인하여 물감을 섞는다.
    for(int i = 0; i < 3; i++)
    {
        moon[i] = 0;

        for(int j = 0; j < size; j++)
        {// 혼합할 모든 물감의 R or G or B를 섞은 후
            moon[i] += paint[perm[j]][i];
        }
        // 물감의 갯수로 나눈다.
        moon[i] /= size;
    }
}

int Gap()
{// 곰두리색 혼합된 색의 차이를 반환한다.
    int gap = 0;
    for(int i = 0; i < 3; i++)
        gap += abs(gom[i] - moon[i]);
    return gap;
}

void permutation(int cnt, int limit, int start)
{
    if(cnt == limit)
    {// 조합의 원소 갯수가 limit과 같아지면
        setMoon(limit); // 색을 섞은 후,
        ans = min(ans, Gap()); // ans를 차이가 최소가 되는 값으로 갱신한다.
        return;
    }
    
    // start 인자를 통해 중복을 방지한다.
    
    for(int i = start; i < n; i++)
    {// 조합 생성
        perm[cnt] = i;
        permutation(cnt + 1, limit, i + 1);
    }
}

void SOLVE()
{
    for(int i = 2; i <= n; i++)
    {
        if(i > 7) break; // 미미는 아직 실력이 부족하여 최대 7개의 색만을 혼합할 수 있다.
        permutation(0,i, 0); // i개의 물감을 섞는다.
    }

    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

GOLD5 미만 난이도는 알고리즘 및 풀이 설명을 주석으로 대체합니다.
주석을 참고해주세요.