BAEKJOON_6064) 카잉 달력

BAEKJOON

# 단계8 # 2019 SW역량테스트준비-연습

# 규칙 찾기 # 브루트 포스 # 건너 뛰며 해보기

6064) 카잉 달력 (19.01.22) (19.10.04)

* 처음 풀 때, x나 y중에 하나 고정시켜야 할 것 같다고 했는데, 이번에 풀 때 방법을 알았다.
* m이 x인 경우만 살펴보면 되는거였는데, 처음 시작을 x로 하고, m을 더해서 다음 x를 찾았다.
* i는 m과 n의 최소공배수까지 돌렸다. m,n이 최소공배수 번째이기 때문이다.
* 이때 n의 값이 y인 경우는 i를 n으로 나눴을 때 나머지가 y인 경우다.

* 그냥 x, y 그대로 썼더니 10, 12에서 10, 12를 구할 수 없었다.
* 최소공배수니까 나머지가 0이 나와서였는데,
* x, y를 1씩 빼줘서 구하고자 하는 값의 전번째를 구한다음에 1을 더해줬다.



* 문제를 처음 본 날은 그냥 패스..

* 일단은 규칙 찾기 타이틀을 가진 문제니까, 일단 여러 각도에서 그려봤다.
* 결과적으로 x를 한 줄로 세우고, 옆에 가능한 y 의 값들을 적었더니 알 수 있었다.
* y의 개수는 m과 n의 최소공배수. 그 안에 구하려는 y가 존재하면,
* 몇번째에 나왔는지, 그리고 x의 값은 무엇인지를 사용해 답을 구했다.



* 여기서 위의 방법으로 풀었는데, 이 코드가 처음에 계속 틀렸다고 했다.
* 분명 예제도 다 맞게 나오고, 임의로 넣은 값들도 제대로 나와서 골치아파하던때,
* https://www.acmicpc.net/board/view/21503
* 여기서 반례 목록을 보고 수정하면서 틀린 점을 알 수 있었다.



* 8 2 4 2 에서
* n 값이 m보다 작아서 계속 반복적으로 n이 들어갈 때
* 그걸 캐치하지 못하고, 다른 숫자를 계산했던 거였다.

* 그리고 이걸 바탕으로, 6 4 5 3 이라는 예시를 생각하고
* 어떻게 하면 첫번째 숫자를 바르게 얻을 수 있을지 찾았다.

* 또 이런 문제를 푼다면 더 빠르게 해결할 수 있을까...?

* 문제를 파악하자마자로 돌아가서..
* 처음에는 그냥 x, y를 p, q를 사용해 증가해나가면서 일치하는 순간을 찾으려 했었는데,
* 계속 시간초과가 나왔다.



* 이 코드에서 왜 자꾸 시간초과가 나는지, break를 걸어야 할 다른 경우가 있는지를 찾지 못했고,
* 새로 만들어보자 해서 다시 짠 코드로 정답을 맞출 수 있었다.
* x, y 중 하나를 고정시켜야 하는 것 같았다.