[BOJ/C++] 6064 카잉 달력

문제 링크 https://www.acmicpc.net/problem/6064

📝 문제

문제 설명
최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

💻 코드

#include <iostream>
using namespace std;

int solve(int M, int N, int x, int y) {
    while (x <= M * N) {
        if ((x-y) % N == 0) {
            return x;
        }
        x += M;
    }
    return -1;
}

int main()
{
    int T, M, N, x, y;
    cin >> T;
    
    for (int i=0; i<T; i++) {
        cin >> M >> N >> x >> y;
        cout << solve(M, N, x, y) << "\n";
    }
    
    return 0;
}

📌 해결방법

1. 해를 k라고 했을 때 (k-x) 가 M의 배수이면서 (k-y) 가 N의 배수인 값을 찾기
   → (k-x) % M == 0 and (k-y) == 0 조건을 만족하는 k 값
2. 결국 x에 M 계속 더한 값 = y에 N을 계속 더한 값
   → (x-y) % N != 0 이면 x += M

💡 배운 점

• C++은 함수의 인자에까지 자료형을 표시해야 하는구나.....

---

✔ 느낀 점

이거는 파이썬으로 먼저 풀었던 문제였다. 처음에는 파이썬에서 함수를 사용하지않고 flag를 사용해서 구현하였는데, 함수를 사용하는 것이 코드가 더 깔끔할 것 같아서 코드를 수정했었다.

# flag 사용
    flag = 1
    while x <= M * N:
        if (x - y) % N == 0:
            flag = 0
            print(x)
            break
        x += M

    if flag:
        print(-1)
        
# 함수 선언
def solve(M, N, x, y):
    while x <= M * N:
        if (x - y) % N == 0:
            return x
        x += M

    return -1

이거 하나 수정했는데 위 사진처럼 시간이 반토막난것을 보고 C++ 속도가 궁금하기도 하고, c++로 아직 함수문제를 풀어본적이 없어서 도전해보았다.
결과는.............................

오늘의 결론 : C++ 짱빠르니까 짱좋다😎