반응형
programmers.co.kr/learn/courses/30/lessons/42862
greedy문제였습니다.
풀이방법
1. 학생별 체육복 보유 여부를 판별하기 위한 vector선언
2. 체육복을 잃어버린 학생들은 해당 vector의 index를 0으로 만들어줍니다.
3. 그 후 체육복 여분을 가지고 학생의 index를 1씩 증가시켜줍니다.
4. n까지 학생들을 loop를 돌며 확인합니다.
만약 i번째 학생이 체육복이 없다면
양 옆 여분이 있는 학생(체육복 보유개수 2)을 확인 한 뒤 i번째 학생에게 체육복을 빌려줍니다.
만약 i-1번째 학생의 체육복 보유 개수가 2개라면 i-1, i번째 학생의 체육복 보유현황은 1입니다.
만약 i+1번째 학생의 체육복 보유 개수가 2개라면 i+1, i번째 학생의 체육복 보유현황은 1입니다.
5. 갱신이 완료된 vector를 돌며 체육복 개수가 양수라면 ansewr++해준 후 반환합니다.
Code
#include <bits/stdc++.h>
using namespace std;
int solution(int n, vector<int> lost, vector<int> reserve) {
vector <int> student(n+2,1);
int answer = 0;
student[0] = 0;
student[n+1] = 0;
for(int i = 0; i < lost.size(); i++) student[lost[i]]--;
for(int i = 0; i < reserve.size(); i++) student[reserve[i]]++;
for(int i =1; i<=n; i++){
if(!student[i]){
if(student[i-1]==2) student[i-1] = student[i] = 1;
else if(student[i+1] == 2) student[i+1] = student[i] = 1;
}
}
for(auto s : student){
if(s) answer++;
}
return answer;
}
int main(){
vector <int> lost = {1,2,3,5};
vector <int> reserve = {2,4};
cout << solution(5,lost,reserve);
}
Test Case
n = 4
lost = [2]
reserve = [3]
답 : 4
'Algorithm > Greedy' 카테고리의 다른 글
(C++) - 백준(BOJ) 1449번 : 수리공 항승 답 (0) | 2021.02.20 |
---|---|
(C++) - 백준(BOJ) 4796번 : 캠핑 답 (0) | 2021.02.20 |
(C++) - 백준(BOJ) 1931번 : 회의실배정 답 (0) | 2020.09.10 |
(C++) - 백준(BOJ)코딩 11047번 : 동전0 (0) | 2016.12.09 |
(C++) - 백준(BOJ)코딩 1026번 : 보물 (0) | 2016.11.22 |