브루트포스 : 때론 조건을

#6064번 카잉달력 https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

부르트포스 알고리즘이라서 무조건 1씩 더해주면서 연산을 진행하려고 했다.

 

-> 시간초과

 

머리를 굴리다가 도저히 답이 안나와서 또 검색

포인트는 문제를 탐색하는데 들어가는 시간을 어떻게 최소화 시킬 것인지다.

M, N, x, y가 순차적으로 입력되고 K를 구하는 형태인데

K에서 x를 빼면 M의 배수이다.

또 K에서 y를 빼면 N의 배수이다.

 

이 말은 즉

x나 y 둘 중 하나의 값에 M 혹은 N을 계속해서 더해주면 K를 구할 수 있다는 뜻이다

하지만 그렇게 나온 K는 다른 하나(x일 경우엔 y, y일 경우에는 x)의 조건을 충족시켜야한다.

 

첫 번째 예제를 보자.

10 12 3 9

x 를 통해 K를 구하면

 

1)

x + M = 3+10 = 13이다. 하지만 13-9 = 4는 12로 나누어지지 않는다.

즉 13은 12의 배수에 9를 더한 형태로 표현할 수 없다.

 

2) M을 한번 더 더하면

3+20 = 23, 하지만 23-9 =14는 12로 나누어지지 않는다.

 

3) M을 한번 더 더하면

3+30 = 33, 33-9=24는 12로 나누어진다

즉 12*2 + 9 = 33, N과 y로 표현할 수 있다.

 

따라서 정답은 33이다.

 

 

def get_K(M, N, x, y):
    # 연산을 진행하는 x값 자체가 k를 의미하게 된다.
    k = x
    while k <= M*N: # k의 최대값은 M과 N의 최소공배수이다.
        # 하지만 최소공배수를 구하는 연산을 추가하면 시간초과.
        # 구하기 쉬운 아무 공배수나 적용하면 된다.
        if (k-x)%M==0 and (k-y)%N == 0:
            return k
        k += M

    return -1


for _ in range(int(input())):
    M, N, x, y = map(int, input().split())
    print(get_K(M, N, x, y))

 

나는 문제를 볼 때 문제에서 요구하는 기능을 어떻게 구현할까에 대한 고민만 했던 것 같다.

조금 더 수학적인 접근이 필요하다고 느꼈다.

 

문제에서 요구하는 조건은 두가지였다

1) M의 배수와 x의 합으로 표현될 수 있는가?

2) N의 배수와 y의 합으로 표현될 수 있는가?

3) 그 수는 M과 N의 최소공배수(최댓값) 이내의 수인가?