Baekjoon) 6064 카잉달력 - Python , 브루트포스

💭 나의 접근 방법

---

M,N,x,y = M계산 값, N계산 값, x M나머지, y N나머지

 

1. x+(M*i) 를 반복해서 M으로 나눈값이 x 값인지 확인, y+(N*i) 를 반복해서 N으로 나눈값이 y 값인지 확인

2. 1부터 M,N의 최소공배수 값까지 전체탐색하여 구할수 있는지 확인

 

먼저 나는 2번의 방법으로 접근해보았다.

# 6064 카잉달력 S1 

# 틀렸습니다. + 1~ 전체 탐색은 시간 초과문제가 발생함
def gcd(a,b):
    while b > 0:
        a,b = b,a%b
    return a

T = int(input())
for _ in range(T):
    M,N,x,y = map(int,input().split())
    lcd = M*N//gcd(M,N)
    for i in range(1,lcd+1):
        if i % M == x and i % N == y or i % M == 0 and i % N == 0:
            print(i)
            break
    else:
        print(-1)

일단 유클리드 호제법으로 최소공배수를 구하고 그 값까지 전체 탐색을 했다. -> 시간 초과 문제 + 틀렸습니다가 뜸

따라서 1번 방식으로 진행해야한다.

 

💡 결과

---

# +M +N 해서 나머지가 같은 값
T = int(input())
for _ in range(T):
    M,N,x,y = map(int,input().split())
    f = 1
    while x <= M*N:
        if x % N == y % N: # x를 N으로 나누어주어 y와 같은지 확인
            print(x)
            f= 0
            break
        x += M
    if f:
        print(-1)

 x를 M으로 더해 반복문을 실행하고 x % N == y % N 인 경우를 찾으면 되는 방식이다.

 

 

💫 느낀점

---

x에서 M으로 나머지를 구하고, y에서 N으로 나머지를 구해 각각 계산을 하려고 했지만 어차피 정답값만 확인하면 하나의 값(M or N)만 이용해서 나머지를 구해 답을 도출할수있는 문제였다. 시간 초과도 잘생각해서 최적의 방법을 찾도록 더 고민할것!!

 

 

 

6064번: 카잉 달력