체육복

들어가는 말

체육복을 도난당했다. 하지만, 여벌을 가지고 있는 사람이 도난당한 사람에게 체육복을 빌려줄 수 있다. 단, 체육복을 빌려주는 것은 인접한 번호끼리며 여벌을 가진 사람이 체육복을 도난당할 수 있다. 후자의 경우 체육복이 하나뿐이라 다른 이에게 빌려주지 못한다.
그리디 알고리즘이라고 하는데, 왜 탐욕법인지 모르겠다. 탐욕 알고리즘하면 거스름돈 주기나 배낭 싸기를 생각해서 그런가. 이게 왜 탐욕..? 이러면서 풀었다.

코드 설명

학생에게 전부 체육복을 하나씩 준다. 도난당한 만큼 빼주고 여별만큼 더해주면 배열 준비는 끝이다. 0부터 배열의 마지막까지 돌려주면서, i가 0보다 크고 값이 0일 경우 앞의 값이 2인지 확인해서 계산해 준다. else if도 엇비슷하게, 하지만 값이 0인 경우를 포함해주어서 푼다.
i가 0일 경우를 생각하지 못해서, 막혔다. 다른 사람의 풀이를 봤는데, 처음부터 배열을 35로 넉넉하게 지정한 후 i를 1부터 돌려준다. 그렇게 되면 맨 앞이 0일 경우 자연스럽게 뒤에있는 학생의 것을 가지고 오게 된다.
if(student[i] == 0){
if(student[i-1] == 1){}
else if(student[i+1] == 1){}
}
이렇게.
처음에 나도 위의 문제처럼 풀었지만, 값이 안 나온 이유는 0번째(학생으로는 1번쩨)를 처리하지 못했기 때문이다.

코드

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    vector<int> student;
    int front, back;
    
    for(int i=0; i<n; i++){
        student.push_back(1);
    }
    for(int i=0; i<lost.size(); i++){
        student[lost[i]-1]--;
    }
    for(int i=0; i<reserve.size();i++){
        student[reserve[i]-1]++;
    }
    
    for(int i=0; i<student.size(); i++){
        if(i>0 && student[i]==0 && student[i-1]==2){
            student[i]++;
            student[i-1]--;
        }else if(i<n-1 && student[i]==0 && student[i+1]==2){
            student[i]++;
            student[i+1]--;
        }
    }
    
    for(int i=0; i<student.size(); i++){
        if(student[i]>0){
            answer++;
        }
    }
    return answer;
}

P.s

이 문제가 그리디 알고리즘인 이유는 앞뒤에서 가능한 최적의 것만 뽑아서 그런 거 같다. 완전 탐색처럼 전부 계산하지는 않으니...