[백준] 10837 동전 게임

출처 : KOI 2015 고등부 1번, KOI 2015 중등부 1번

풀이

특별한 알고리즘 없이 규칙만 알면 잘 풀리는 문제다. 영희가 동수보다 먼저 동전을 던지기 때문에 동수는 남은 라운드+1 만큼의 점수를 더 얻을 수 있다. 따라서 이러한 특성을 영희의 점수가 동수의 점수보다 더 클 때 적용시켜 주면 된다.

#include<iostream>

using namespace std;
int main(){
    int k,c;
    cin>>k>>c;

    for(int i=0;i<c;i++){
        int a, b;
        cin>>a>>b;

        int restRound=k-max(a,b);
        if((a >= b && a - restRound- b > 2) || (a < b && b - restRound- a > 1)){
            cout<<"0\n";
        }
        else{
            cout<<"1\n";
        }
    }
}    

이렇게 코드를 작성하면 Code UP에서는 정답 처리가 되나 백준에서는 시간 초과가 발생한다.

시간 복잡도는 O(n)이기 때문에 알고리즘 상에 문제는 없어 고민을 좀 했었다. 혹시나 하는 마음에 cin을 scanf()로, cout을 printf()로 하여 코드를 짜니 정답 처리가 되었다.

#include<stdio.h>

int max(int a, int b){
    return a>b?a:b;
}
int main(){
    int k,c;
    scanf("%d %d",&k,&c);

    for(int i=0;i<c;i++){
        int a, b;
        scanf("%d %d",&a,&b);

        int restRound=k-max(a,b);
        if((a >= b && a - restRound- b > 2) || (a < b && b - restRound- a > 1)){
            printf("0\n");
        }
        else{
            printf("1\n");
        }
    }
}