BOJ 6064: 카잉 달력

오늘의 문제! 카잉 달력이다.

문제를 보자마자, 저번에 풀었던 문제 (https://www.acmicpc.net/problem/1476)와 굉장히 비슷하다고 느꼈다.

하지만, 절대 같지 않았다.

 

우선 오답코드부터 보자.

n=int(input())
for i in range(n):
  n,m,ansX,ansY=map(int,input().split())
  x=1
  y=1
  year=1
  while True:
    if x==ansX and y==ansY:
      print(year)
      break
    if x==n and y==m:
      print(-1)
      break
    if x==n:
      x=1
    else:
      x+=1
    if y==m:
      y=1
    else:
      y+=1
    year+=1

이렇게 단순하게 하나하나 더하면서 구하면, 시간 초과가 뜨게 된다.

아쉽다... 이렇게 간단하면 얼마나 쉬울까?

---

이것 또한 실패 코드이다.

하지만 알고리즘을 새로 발견했다.

n=int(input())
for i in range(n):
  n,m,x,y=map(int,input().split())
  findvalue=False
  while x<=n*m:
    if x%m==y:
      findvalue=True
      print(x)
      break
    x+=n
  if findvalue==False:
    print(-1)

<10,12> 인 달력일 때, <3,9>이 목표값이라고 치자.

n이 10인 달력이면, 3일때, 13일때, 23일때 모두 같은 년으로 치지 않겠는가.

그러면 3일때, 10일때, 23일때 모두 12로 나누면 9라는 나머지가 나오면 x,y값을 동시에 만족하지 않겠는가!!!

 

라고 생각을 했지만, 50프로만 맞았다.

왜냐하면, <1,1>인 달력일 때 <1,1>이라는 목표값이 있으면,

1을 1로 나누면 나머지가 0이다......ㅠ

m, n, x, y의 값이 같아질 때가 문제이다.

 

그렇기에, 정답 코드! 를 보겠다.

n=int(input())
for i in range(n):
  n,m,x,y=map(int,input().split())
  findvalue=False
  while x<=n*m:
    if (x-y)%m==0:
      findvalue=True
      print(x)
      break
    x+=n
  if findvalue==False:
    print(-1)

x와 y의 값을 빼서, m으로 나누기로 했다.

결국에는 같은 효과이다.

<10,12>인 달력의 <3,9> 년인 달력을 다시 보자.

3-9 를 12로 나누고,

3에 10을 더하고, 13

13-9를 12로 나누고,

13에 10을 더하고, 23

23-9를 12로 나누고,

23에 10을 더하고, 33

33-9에 12로 나누고.

이런 느낌이다.

<1,1> <1,1> 같은 경우에도,

1-1을 1로 나누면 나머지가 0이다.

 

깔끔하다.

 

어려운 문제지만, 알고리즘을 알고 나니 정말 재밌어지는 것 같다.