[레벨1] 체육복

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    int i;
    vector<int> tempv(n + 1,1); // n명의 학생은 모두 체육복이 하나씩 있다.
    
    // 총 0,1,2라는 값의 경우가 나옴.
    for(i = 0; i < lost.size(); ++i)
    {
        tempv[lost[i]]--; // 도난당한 학생은 체육복 수 -1.
    }
    for(i = 0; i < reserve.size(); ++i)
    {
        tempv[reserve[i]]++; // 여벌의 학생은 체육복 수 + 1.
    }
    
    // 빌려주는 작업
    for(i = 1; i < tempv.size(); ++i)
    {
        if(tempv[i] == 0) // 체육복이 없다.
        {
            // 앞 뒤 체크.
            if(i - 1 != 0 && tempv[i - 1] == 2)
            {
                tempv[i]++;
                tempv[i - 1]--;
                continue;
            }
            if(i + 1 < tempv.size() && tempv[i + 1] == 2)
            {
                tempv[i]++;
                tempv[i + 1]--;
                continue;
            }
        }
    }
    for(i = 1; i < tempv.size(); ++i)
    {
        if(tempv[i] > 0)
            answer++;
    }
    
    
    return answer;
}

 

 

그리디 알고리즘 문제라고 한다.

 

그리디 알고리즘은 경우의 수가 존재하고 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘.

즉 그 순간에 최선이라고 생각하는 좋아보이는 쪽을 선택하는 것. 그렇기에 항상 그 선택이 최적이라고 할 순없다고 한다.

 

그렇기에 어떻게 잘 풀까?를 생각하기 보단 일단 생각나는대로 문제를 풀어보았다.

 

위 문제는 학생들이 가지고 있는 체육복의 경우의 수만 생각하면 어렵지 않은 문제.

모든 학생들이 체육복을 하나씩 가지고있었지만, 도난을 당한 학생이나 여벌을 가져온 학생을 생각해보면

 

도난을 당해 체육복이 없는 학생 = 0

도난을 당했지만 여벌 체육복이 존재했던 학생 = 1

도난을 당하지 않고 여벌 체육복 마저 존재하는 학생 = 2

 

이 경우 빌려줄 수 있는 학생은 마지막이며 빌려줘야할 대상은 맨 위. (1이라는 경우의 수는 배제가 가능)