글 읽기 - [C++] 카잉달력 반례좀 부탁드립니다.

shumin 7년 전 0

간단하게 제가 생각한 알고리즘을 설명하자면

주어진 x에다가 M 값을 최소공배수까지 더하면서

1 - if 구문

% N 의 값을 y와 비교하여 만약 같을 경우 그 값 (전체 년수)를 출력하고,

2 - else if 구문

% N 연산은 y가 N와 같은 값일 경우 0을 출력하기 때문에 추가함.

모든 예제 입력에 대해서 예제 출력과 같이 나오는데

이유를 잘 모르겠습니다. 고수분들의 제 소스의 반례를 부탁드리겠습니다.

#include <iostream>                                                                                                                  
#include <algorithm>

using namespace std;

int getGCD(int x, int y)
{
    if(y == 0)
        return x;
    else
        return getGCD(y, x%y);
}

int getLCM(int x, int y)
{
    return (x * y) / getGCD(x, y); 
}

int main()
{
    int num;
    cin >> num;

    while(num--)
    {   
        int M, N, x, y;
        cin >> M >> N >> x >> y;
        int last_year = getLCM(M, N); 
        bool isValid = false;

        if(M < N)
        {   
            swap(M, N); 
            swap(x, y); 
        }   

        for(int i=x; i<=last_year; i+=M)
        {   
            if(i % N == y)
            {   
                cout << i << endl;
                isValid = true;
                break;
            }   
            else if(i % N == 0 && i % y == 0)
            {   
                cout << i << endl;
                isValid = true;
                break;
            }   
        }   

        if(isValid == false)
            cout << "-1" << endl;
    }   

    return 0;
}

chogahui05 7년 전 1

간단하게 반례 들어드릴게요.

13 11 9 2

답 35

chogahui05 7년 전 1

제가, 어떤 알고리즘을 어떻게 쓰고 어떻게 시간 단축을 해야 하느냐를 알려드리면

그냥 답을 알려드리는 것과 같잖아요.

힌트로 어떻게 카잉 달력이 돌아가는지 넣어놓았습니다. 규칙을 잘 찾으시면 감이 오실 거에요.

힌트는 x, y를 같이 생각하지 마시고 먼저 따로 생각해 보시라는 겁니다. 그러면 규칙이 보이실 거고

방정식이 하나 세워지실 거에요.

shumin 7년 전 1

반례 정말 감사합니다.

덕분에 해결했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[C++] 카잉달력 반례좀 부탁드립니다.

shumin 7년 전 0

chogahui05 7년 전 1

chogahui05 7년 전 1

shumin 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말