백준 1713번 후보 추천하기 C++

문제 링크 : https://www.acmicpc.net/problem/1713

1713번: 후보 추천하기

 

 문제 풀이

 이 문제에서는 사진틀의 개수와 추천횟수를 주고, 어떤 학생들을 추천했을 때 사진틀에 있는 사진들이 바뀌어 최종적으로 어떻게 되는지 묻고 있다.

 

 나는 이 문제를 풀 때 여러 함수를 정의해서 풀었다. 먼저 사진틀에 사진들이 다 차있는지를 알아보는 full()과, 삭제할 학생을 찾는 remove(), 매 추천마다 사진틀의 시간을 더해주는 addTime()함수를 정의하였다. 

 먼저 full()함수는 비어있는 것이 존재할 경우 false를 리턴하고, 아닌 경우 true를 리턴하면 되기 때문에 어렵지 않다. remove()함수는 사진틀에 있는 학생들의 추천횟수를 비교해, 추천횟수가 최소인 학생을 찾아주면 된다. 근데 만약 이전까지의 최소와 같은 추천횟수를 갖는 경우에는 걸려있던 시간이 더 긴 경우에만 min을 업데이트 해준다. 마지막으로 addTime()함수는 단순히 사진틀에 있는 학생들의 시간맘ㄴ 추가해주면 되므로 이것도 어렵지 않다.

 이제 main함수에서 사진틀이 찬 경우와 안 찬 경우로 나누어, 이 함수들을 잘 활용해주면 답이 잘 나온다.

 

시행 착오

 마지막에 출력 부분에서 sort를 해주고 출력을 하는데, 최종적으로 사진틀이 꽉 차있지 않은 상황을 고려하지 못했다. 예를 들어서 사진틀의 개수가 3개인데, 1번 학생만 추천을 받은 경우 사진틀 배열은 {1 0 0}이 된다. 여기서 그냥 sort를 하고 출력하는 경우, 1이 아니라 0 0 1이 출력되서 오류가 있었다. 그래서 출력 부분에서 0이 아닌 경우만 출력하는 것으로 바꾸었다.

 

 

코드

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

int pic[21],stu[101],t[101],N;

bool full()
{
    for(int i=1;i<=N;i++)
    {
        if(pic[i]==0)
        {
            return false;
        }
    }
    return true;
}
int remove()
{
    int mn = 1001,mn_i,mx_t=0;
    for(int i=1;i<=N;i++)
    {
        if(mn > stu[pic[i]])
        {
            mn = stu[pic[i]];
            mn_i = i;
            mx_t = t[pic[i]];
        }
        else if(mn==stu[pic[i]]&& mx_t < t[pic[i]])
        {
            mn = stu[pic[i]];
            mn_i = i;
            mx_t = t[pic[i]];
        }
    }
    return mn_i;
}

void addTime()
{
    for(int i=1;i<=N;i++)
    {
        if(pic[i]==0)
        {
            break;
        }
        else
        {
            t[pic[i]] ++;
        }
    }
}

int main()
{
    int rec_n,rec_stu;
    cin>>N>>rec_n;
    
    while(rec_n--)
    {
        cin>>rec_stu;
        if(stu[rec_stu] != 0)
        { 
            stu[rec_stu] ++;
            addTime();
            continue;
        }
        stu[rec_stu] ++;
        
        //꽉차지 않은 경우
        if(!full())
        {
            for(int i=1;i<=N;i++)
            {
                if(pic[i]==0)
                {
                    pic[i] = rec_stu;
                    break;
                }
            }
            addTime();
            continue;
        }
        
        //꽉찬 경우
        int remove_stu = remove();
        stu[pic[remove_stu]] = 0;
        t[pic[remove_stu]] = 0;
        pic[remove_stu] = rec_stu;
        addTime();
    }
    
    sort(pic,pic+N+1);
    for(int i=1;i<=N;i++)
    {   
        if(pic[i]!=0)
        {
            cout<<pic[i]<<" ";
        }
    }
}