[백준][Java] 6064번 카잉 달력

너무 어려웠습니다.

반례 예시는 해당문제의 질문검색 나와있는

https://www.acmicpc.net/board/view/21503 를 참조하였고

알고리즘의 전반적인 틀은

http://andamiro25.tistory.com/93 를 참조하였습니다.

문제에서 요구하는 (x,y)가 몇 번째 해인지 찾는 가장 쉽고 무식한 방법은

N부터 1씩 증가하시키는 경우입니다. 하지만 M,N의 최대값이 40000이기 때문에

while문을 최대 40000*40000번을 돌리는 경우가 생겨

시간초과할 것이 분명하므로 패스하였습니다.

도저히 풀이법을 못찾아서 구글링하다 찾은 방법은

<x:y>의 x와 y중 작은 값 하나를 고정시키는 방법입니다.

이를 이용하면 while문은 최대 약 40000번까지만 돌리면 모든 경우의

수를 해결할 수 있습니다.

이 방법을 알고도 제가 정의를 실수한 부분은

m_n=((m_n+smaller_unit)%bigger_unit==0)?bigger_unit :(m_n+smaller_unit)%bigger_unit ;

이 부분인데 기존에는

m_n= (m_n+smaller_unit)%bigger_unit

이런식으로 정의해서

 12 6 12 6 인 경우에 x의 값이 0이 되는

경우를 간과한 것입니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int k = sc.nextInt(); int [][]input = new int[k][4]; int []res = new int[k]; for(int i=0; i<k; i++) { for(int j=0; j<4; j++) { input[i][j] = sc.nextInt(); } } for(int i=0; i<k; i++) { int m_n=0; int count =0; int bigger_unit,smaller_unit, final_mn; if(input[i][2]>=input[i][3]) { m_n=input[i][3]; res[i]=input[i][3]; bigger_unit = input[i][0]; smaller_unit = input[i][1]; final_mn=input[i][2]; } else { m_n=input[i][2]; res[i]=input[i][2]; bigger_unit = input[i][1]; smaller_unit = input[i][0]; final_mn=input[i][3]; } while(true) { if(m_n==final_mn) { res[i]+=count*smaller_unit ; break; } else if(count==bigger_unit) { res[i]=-1; break; } else { count++; m_n=((m_n+smaller_unit)%bigger_unit==0)?bigger_unit :(m_n+smaller_unit)%bigger_unit ; } } } for (int i : res) { System.out.println(i); } } }