백준 12915 - 대회 개최

www.acmicpc.net/problem/12915

 

5개의 난이도에 해당하는 문제 수가 주어질 때 최대로 개최할 수 있는 대회의 수를 구해야 하는 문제이다.

 

대회를 개최하기 위해서는 쉬움, 중간, 어려움 난이도의 문제가 하나씩 배정되어야만 한다.

 

매개변수로 주어지는 e, m, h는 배정될 수 있는 난이도가 한가지로 정해져 있으므로 나머지 em, mh에 대해 난이도를 적절히 분배하는 방법을 찾는게 핵심이다.

방법

1. 남아있는 e, m, h를 우선적으로 배정하도록 한다.

 

2. 남아있는 e, m, h가 없을 경우 em, mh 중에서 배정하도록 한다.

 

2 - 1. 쉬움은 em을 주고 어려움은 mh를 주면 되는데 중간의 경우는 em과 mh중 더 많이 남아있는 문제를 배정하고 만약 두 난이도가 동일한 갯수만큼 남아있으면 em을 할당해주도록 한다.

em을 먼저 배정해야 하는 이유

쉬움에 이미 한개가 배정되어 있고 남은 문제가 em과 mh가 각각 한개씩 남아있다고 하자.

 

이 때 m에 mh를 배정할 경우 em이 남게 되고 어려움에 문제를 배정할 수 없게 되어 최적해에 도달 할 수 없게 된다.

 

어려움 -> 쉬움순으로 문제를 채워 나가려고 할 때에 중간 난이도에 배정하는 방법은 em == mh 일때 mh를 먼저 배정해주는 것 역시 최적해에 도달하게 될 수 있음을 알 수 있다.

 

전체 코드

#include <iostream>

using namespace std;

int res;

int main()
{
    int e, em, m, mh, h;
    cin >> e >> em >> m >> mh >> h;
    
    while (1)
    {
        bool e_pass = false, m_pass = false, h_pass = false;
        if (e)
            --e, e_pass = true;
        else
            if (em)
                --em, e_pass = true;
        
        if (m)
            --m, m_pass = true;
        else
            if (mh || em)
                if (em >= mh)
                    --em, m_pass = true;
                else
                    --mh, m_pass = true;
        
        if (h)
            --h, h_pass = true;
        else
            if (mh)
                --mh, h_pass = true;
        
        if (!e_pass || !m_pass || !h_pass)
            break;
        ++res;
    }
        
    cout << res;
}