[프로그래머스] 체육복 (C++)

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/42862

코딩테스트 연습 - 체육복

1. 주의할 점

- 그리드 알고리즘으로, 상황에 맞게 잘 설계한다

 

2. 구현

- 처음엔 DFS를 통해 해결했지만, 굳이 DFS를 사용하지 않아도 될것 같다

- Arr[] 배열을 통해 현재 보유한 체육복 수 -1만큼 저장한다

- For문을 통해 만약 현재 체육복 미소지자면 양옆 사람을 확인하여 대여가 가능하다면 대여를 한다.

- 이후, 현재 체육복을 1개 이상 보유하고 있다면 Answer++를 수행한다

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int arr[32];

int solution(int n, vector<int> lost, vector<int> reserve) {
    int answer = 0;
    for(int i: lost)
        arr[i]--;
    for(int i: reserve)
        arr[i]++;
    for(int i=1;i<=n;i++){
        if(arr[i]==-1){
            if(arr[i-1]==1)     arr[i-1]=arr[i]=0; 
            else if(arr[i+1]==1)    arr[i+1]=arr[i]=0;
        }
        if(arr[i]>=0)answer++;
    }
    return answer;
}