백준 6064. 카잉 달력

https://www.acmicpc.net/problem/6064

6064번: 카잉 달력

 

M,N 값이 최대 4만이므로 일일히 수를 증가시켜 가면서 찾으면 O(40000 * 40000 = 1600000000) O(16억)으로 시간초과가 나게 된다.

패턴은 숫자들을 나열해 보면 알 수 있다.

 

M=10, N=12 일때

 

1:1	1:11	1:9
2:2	2:12	2:10
3:3	3:1	3:11
4:4	4:2	4:12
5:5	5:3	5:1
6:6	6:4	6:2
7:7	7:5	7:3
8:8	8:6	8:4
9:9	9:7	9:5
10:10	10:8	10:6

 

표를 보면 M,N 중 작은 값에 해당하는 년도는 최대년도 까지 이어지고

그 반대 년도는 각 열 마다 (M-N) 만큼 차이가 난다.

예를들어

1행2열은 1:11 이고 

1행3열은 1:9 (11에서 M-N인 2를 뺀값) 이다.

 

따라서 x=3, y=9이 몇년도인지 찾으려면 

3:3에서 y값 3을 9가 나올때까지 2씩 몇뻔씩 빼야되는지 찾으면 된다.

 

 

---

2022.02.20

 

두 개의 숫자가 다른 진법을 사용하고 볼 수 있고 퍼센트 연산을 이용할수 있다.

먼저 두 숫자를 '일'을 기준으로 고정시켜 놓고 

그 후에 '월'을 증가시켜 나간다.