[BOJ/백준] 6064 카잉 달력

● [문제번호 6064] 카잉 달력

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

6064번: 카잉 달력

 

● 알아야 할 것

: 브루트 포스 (Brute Force)

: 최대공약수, 최소공배수 (유클리드 호제법)

 

● 풀이 과정

: 이전에 있던 [1476 날짜계산] 과 비슷한 문제다.

대신 최소공배수와 시간복잡도를 줄이기 위한 고려 사항이 추가되었다.

시간복잡도를 줄이는 방법이 마땅히 떠오르지 않아 구글링하였다.

 

: 각 테스트케이스의 마지막 해는 M, N의 최소공배수 이다.

따라서 k번째 해를 구할 때 최소공배수를 구해야한다.

(유클리드 호제법 이용)

 

● 주의 할 것

: 그냥 1년부터 마지막 해까지 반복문을 이용하면 '시간 초과' 결과가 나온다.

 

이를 해결하기 위해 반복문을 수정해야하는데,

x와 y 둘 중 하나를 선택하여 (무엇을 선택하든 상관없음)

 

(x 선택했다 가정)

 

k번째 해를 M으로 나눴을 때 나머지가 x인 해는

{x}, {x + (M * 1)}, {x + (M * 2)}, {x + (M * 3)}, ... 이므로

결국 반복문을 x부터 시작해서 M씩 증가해도 문제되지 않는다.

(오히려 x를 고려하지 않아도 되므로 편리 / 풀이코드에서는 그냥 고려하는 코드 추가함)

 

● 참고 할 것

: 풀이과정

https://transferhwang.tistory.com/308

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int T, M, N, x, y;

// 최대 공약수 구하기
int gcd()
{
    int a = max(M, N);
    int b = min(M, N);
    
    while(b != 0)
    {
        int temp = a % b;
        a = b;
        b = temp;
    }
    
    return a;
}

// 최소 공배수 구하기
int lcm()
{
    return M * N / gcd();
}

// k번째 해 구하기
int year()
{
    int end = lcm();
    
    // for(int i = x; i <= end; i += M) 이든
    // for(int i = y; i <= end; i += N) 이든 상관없다
    // 시간 초과를 막기 위해 사용
    for(int i = x; i <= end; i += M)
    {
        int tempx = i % M;
        if(tempx == 0)
            tempx = M;
        int tempy = i % N;
        if(tempy == 0)
            tempy = N;
        if(tempx == x && tempy == y)
            return i;
    }
    
    return -1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> T;
    
    for(int t = 0; t < T; t++)
    {
        cin >> M >> N >> x >> y;
        
        cout << year() << "\n";
    }

    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [500 - 브루트 포스] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	2309	일곱 난쟁이	https://pirateturtle.tistory.com/228
2	3085	사탕 게임	https://pirateturtle.tistory.com/229
3	1476	날짜 계산	https://pirateturtle.tistory.com/230
4	1107	리모컨	https://pirateturtle.tistory.com/231
5	14500	테트로미노	https://pirateturtle.tistory.com/232
6	6064	카잉 달력	https://pirateturtle.tistory.com/233
7	1748	수 이어 쓰기 1	https://pirateturtle.tistory.com/234
8	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/235