[브루트포스] 백준 6064번 카잉 달력(C++)

https://www.acmicpc.net/problem/6064

 

6064번 카잉 달력 문제

 

해당 문제는 무슨 국어 비문학 문제처럼 막 엄청 길지만 ,,  자세히 읽어보면 우리가 풀었던 문제다

 

바로

https://lee-soo.tistory.com/9

[브루트포스] 백준 1476번 날짜 계산(C++)

백준 1476번 날짜계산 구성만 다를뿐 완전히 똑같다.

 

단 한가지 다른점이 존재하는데 그것은 바로

 

 

문제에 대한 이해는 1476번을 보고 와주길 바란다.

 

e 와 s 와 m 이 그저 n 과 m으로 변한것이니까.

 

먼저 예를들어 n:2,m:4 일때를 생각해보자

 

그럼 가능한 모든 경우의 수는

1,1

2,2

1,3

2,4

 

인데, 

어 그렇다면 ,1 과 2는 안되고

2,3의 조합은 나올 수 없다는 것이다

 

즉

 

n 과 m 이 2 ,4 고 입력값 두개가 1 , 2 or 2,3일때는

-1이 나온다는 것

 

아.. 순간적으로 머리가 띵해지는군

그래도 어려울 것 없다.

 

먼저 n과 m으로 만들 수 있는 모든 경우의 수를 생각해보자

 

이 뜻이 처음에는 잘 와닿지 않을 수 있으니 간단히 예시를 통해 보여주겠다

 

예를들어 n : 3 이고 m : 8 일때

n자리에 들어올 수 있는 수는 1, 2 ,3

m자리에 들어올 수 있는 수는 1,2,3,4,5,6,7,8

 

총 24가지 경우의 수가 들어올 수 있다.

 

즉 n * m 의 경우의 수라는 것이다.

 

근데 예를들어 

10과 12라고 생각을 해볼까?

 

1~10 

과 

1~12면

오우 120가지의 경우의수가 존재한다고 생각할 수 있는데

 

정답부터 알려주자면 경우의수는 60개밖에 존재하지 않는다.

 

앞선 날짜계산 블로그에서 보여준 것을 생각하면

각 값은 동시에 1씩 증가한다

 

그렇다면 언젠간 한바퀴를 돌아

1....

 

10 ,12가되고난 후

1 1로 돌아오는 시점이 될 것 아닌가?

 

근데 10 12가 1 1 로 다시 돌아오는 시점은 언제일까?

 

먼저 당연히 n * m 번을 돈 경우에는 맞지만

 

더 적은 경우의 수가 있을 것 같다

 

바로 60이다

 

왜냐면?

 

1~10 6번 돌고

1~12 5번 돌면

 

다시 1로 돌아오는 것이다

 

만약 잘 와닿지 않는다면 모든 경우의수를 직접 써보길 권장한다

 

쩃든 이것은 최소공배수라는 것을 잘 알것이다.

 

그렇다면 최소 공배수를 넘어갔는데도,,, 값이 나오지 않는다? = 나올 수 없는 수

 

즉 -1을 출력해주면 되는 것이다.

 

그래서 나는 이전에 풀었던 값을 생각하며

 

#include <iostream>

#include <cmath>

using namespace std;

int gcd(int a, int b);

int lcm(int a, int b);

int main()

{

    int count;

    cin >> count;

    while (count--)

    {

        int e, s;

        int n, m;

        cin >> e >> s >> n >> m;

        int k = 1;

        int t_e = 1, t_s = 1;

        int sig = 0;

        while (t_e != n || t_s != m)

        {

            if (k > lcm(e, s))

            {

                sig = 1;

                cout << -1 << "\n";

                break;

            }

            t_e++;

            if (t_e > e)

                t_e %= e;

            t_s++;

            if (t_s > s)

                t_s %= s;

            k++;

        }

        if (sig != 1)

            cout << k << "\n";

    }

}

int gcd(int a, int b)

{

    int c;

    while (b != 0)

    {

        c = a % b;

        a = b;

        b = c;

    }

    return a;

}

int lcm(int a, int b)

{

    return a * b / gcd(a, b);

}

 

 

여기서

아니 선생님 gcd가뭐고 lcm이머에요

라고 생각한다면 이건 그냥 최대공약수와 최소공배수를 구하는 함수이다.

 

이건 크롬에 치면 나보다 훨씬 똑똑하고 멋지고 잘생기고 학력도 높은 네카라쿠배 갈말한 형님들이 정말 자세히 설며응ㄹ 해놓았으니 대충 넘어가자

우리는 최소공배수만 활용하면 되니까

 

그렇다면 이제 이걸 가지고 문제를 풀면!

if (k > lcm(e, s))

이 조건문 하나를 통해서 -1을 표현하면

 

어 뭐야 왤케 쉬워 정답률 27%인데? 나도.. 네카라쿠배 급?

 

 

당장 채점해

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

?

 

 

?

 

 

?

 

 

어라

뭐지

아니..뭔가 잘못됐나 다시 고쳐볼까..

 

 

?

?

 

?

?

..

 

문제나 더풀자

 

 

빠르게 자신에 대한 객관화를 다시 재점검하고

생각을해보았다..

 

시간은 1초...

 

그럼 뭔가 줄여야 되는데

 

lcm에서 문제인가?? ... 이건 아닌데

 

갖은 고민끝에 검색을 결정

 

 

세상엔 똑똑한 사람들 참 많다

 

한 값을 고정시키고 (입력된 x나 y )

(예를들어 n이 10이고 x=4 일때 x=4로 고정)

 

그다음에 n을 계속 더해가면서 보는거지

 

그렇게 되면 1씩 더하는 것이 아니라

10씩 겅중겅중 뛰면서 더해진다는 거지(예시 n=10일떄)

 

어 뭔가 이상한데요 그래도 돼요?

->응

 

왜냐면 예를들어

10 12 3 9가 들어왔다 쳐봐

 

x=3 고정이고

y에 대한 값만 계속 변화시켜주면 되잖아

어짜피 원하는 값은 결국 x=3일때고, 계속 n값을 더해주면 x=3이되니까 괜찮지

y만 잘 바꿔주면

 

k또한 n씩더해주면 돼

그리고k가 임계점을 넘으면 -1이되는거지

 

코드로보여줌

 

#include <iostream>

#include <cmath>

using namespace std;

int gcd(int a, int b);

int lcm(int a, int b);

int main()

{

    int count;

    cin >> count;

    while (count--)

    {

        int n, m;

        int x, y;

        cin >> n >> m >> x >> y;

        int k = x;

        int t_e = x, t_s = x;

        int sig = 0;

       

        while (t_s != y)

        {

            if (k > lcm(n, m))

            {

                sig = 1;

                cout << -1 << "\n";

                break;

            }

            t_s += n;

            t_s = (t_s - 1) % m + 1;

            k += n;

        }

        if (sig != 1)

            cout << k << "\n";

    }

}

int gcd(int a, int b)

{

    int c;

    while (b != 0)

    {

        c = a % b;

        a = b;

        b = c;

    }

    return a;

}

int lcm(int a, int b)

{

    return a * b / gcd(a, b);

}

 

 

흑흑어려워