[BOJ 2875] 대회 or 인턴(반복문없는 if문 풀이, 시간복잡도 최소화)

이 문제는 그리디 알고리즘으로 분류되어 있다.

 

 

 

그리디는, 매순간 최선의 선택을 하는 알고리즘인데 이 문제에서 어떤 의도로 사용하라고 했는지는 잘 모르겠다.

 

 

 

문제를 풀기 위해서 다음의 과정을 거쳤다.

 

 

 

1. 최대 만들 수 있는 팀의 수를 구하기

2. 최대 만들 수 있는 팀 이외의 인원들을 K에 사용하기('-' 연산)

3. 2를 실시한 후에, K에 해당되는 인원이 아직도 남아있다면 팀을 해체시키기

 

 

 

위의 세 과정을 코드로 작성하였다.

 

 

 

구글링을 해보면 대부분 While문을 이용한 코드를 작성했다.

 

 

 

While문을 이용한 코드는 N과 M이 크다면, 시간복잡도가 증가해서 효율성이 떨어지기 때문에, 아래의 코드가 더 효율적이라고 볼 수 있다.

 

 

 

해설코드(C++).

 

#include <iostream>
using namespace std;
 
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    
    int answer;
    if(N / 2 >= M){
        answer = M;
        if(N - (2 * M) < K)
        {
            K -= (N - (2 * M));
            answer -= (K + 2) / 3;    
        }
    }else{
        answer = N / 2;
        if(M - N / 2 < K){
            K -= (M - (N / 2));
            answer -= (K + 2) / 3;
        }
    }
    
    cout << answer << endl;
    return 0;
}