프로그래머스 - 체육복

jihunnit·2022년 9월 10일
0

코테

목록 보기
12/20

체육복

그리디 알고리즘(Greedy algorithm) 문제이다
한국어로는 욕심쟁이 알고리즘 이랬나
번역이 아주 마음에 든다

항상 그 상황에서 조건에 따라 할 수 있는
최선의 작업을 수행하면 된다.

물론 이렇게 직관적이고 쉽고 빠르기에
안 통하는 경우가 있다. 사실 매우 많다.

대표적인 예로는 특정 금액을 이루는 동전 갯수 찾기 문제인데
각각 금액의 동전으로 특정 금액을 만족시켜야 할 때
최소 갯수가 몇개냐는 것이다.

근데 이게 그리디가 안통한다.
예를 들면 1,4,5원 짜리 동전이 있다고 가정하면
그리디 알고리즘을 적용하면 5+1+1+1의 4개가 나오지만
실제로는 4+4 두개가 최소 갯수이다.

(동전 문제의 경우 만족시켜야 하는 금액의 약수인 동전들만 존재해야만 최소 갯수를 맞출 수 있다고 알고있다.)

이렇듯, 이런 최대 최소를 구하는 문제의 케이스를 잘 나눠서
그리디 알고리즘을 적용해야 할 지,
동적계획법을 적용해야 할 지 잘 파악해야 한다.

각설하고, 이 문제에 대해서 얘기를 하자면
그냥 유니폼이 없는 친구를 기준으로 해서
i-1번 친구가 여분이 있는지 체크하고
없으면 i+1 친구의 여분을 체크하고 하면 된다

소스는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    int arr[31]={0};
    for(int i=1;i<=n;i++){
        arr[i]=1;
    }
    for(auto x:lost){
        arr[x]--;
    }
    for(auto x:reserve){
        arr[x]++;
    }
    for(int i=1;i<=n;i++){
       if(arr[i]==0){
           if(arr[i-1]==2&&i-1>=1){
               arr[i-1]--;
               arr[i]++;
           }
           else if(arr[i+1]==2&&i+1<=n){
               arr[i+1]--;
               arr[i]++;
           }
       }
    }
    for(int i=1;i<=n;i++){
        if(arr[i])answer++;
    }
    return answer;
}
profile
인간은 노력하는 한 방황한다

0개의 댓글