그리디 알고리즘을 이용하는 문제이다
탐욕이라는 말처럼 가장 큰것들을 골라서, 가장 작은 것들을 골라서, 가장 빨리 끝나거나 가장 오래 걸리는 것을 골라서 이게 좋아보이네! 하고 선택해서 풀어나가는 것을 그리디 알고리즘이라고 한다
가장 큰 수 들을 우선 선택하여 최소한의 개수로 목표 수를 만들기
낼 수 있는 것 중 하나씩 고를때 최대값들만 골라서 최대값 만들기
가장 빨리 끝나는 수업 순으로 나열하여 수강 수를 최대로 하기
벌금이 다른 여러명이 벌금을 나눠 낼때 벌금이 작은 사람들 순으로 나열하여 총 벌금을 최소로 하기
등등이 모두 그리디 알고리즘의 예시라고 한다
정말 가장 큰거! 가장 작은거! 가장 빨리 끝나는거! 가장 오래 걸리는거! 처럼 욕심부리는 것 같긴하다
처음 풀때 같거나 옆에 있음 인덱스를 양쪽모두 지워서 남는 lost 수 를 n개에서 빼주어 구하려 했으나...
벡터인지라 지우고 빼는걸 구현하다가 자꾸 예외가 발생하였다
다음처럼 배열을 만들어서 카운트를 사용하면 간단한것을... 익숙해질때까지 풀고자 한다
#include <string>
#include <vector>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
int answer = 0;
// 학생별 카운트를 위해 학생수에 조사할 양 옆 2개를 붙여 n+2개의 배열을 만든다
int tok[32]={0};
// reverse를 돌며 요소의 값을 인덱스로 가지는 tok의 요소에 ++ 해준다
for(int i=0; i<reserve.size(); i++){
tok[reserve[i]]++;
}
// 위와 같이 돌며 tok의 요소에 -- 해준다
for(int i=0; i<lost.size(); i++){
tok[lost[i]]--;
}
// tok을 1부터 n까지 돌며 tok의 요소가 0보다 크다면 나눠줄 수 있으므로
for(int i=1; i<=n; i++){
int front = i-1;
int back = i+1;
// 0보다 큰 값을 가지는 요소의 앞이 음수라면 앞의 요소를 ++, 본인 요소를 --
if(tok[i]>0){
if(tok[front]<0){
tok[front]++;
tok[i]--;
}
// 0보다 큰 값을 지니는 요소의 뒤가 음수면 뒤의 요소를 ++, 본인 요소를 --
else if(tok[back]<0){
tok[back]++;
tok[i]--;
}
}
}
// tok 을 전체로 돌며 0이상인(옷이 있는) 학생들을 카운트한다
for(int i=1; i<=n; i++){
if(tok[i]>=0){
answer++;
}
}
return answer;
}
댓글