Cain Calendar

Transformed version of Calculate Date

날짜 계산 문제와 거의 비슷하다고 할 수 있다. 하지만 아래와 같이 Brute Force 를 사용할 수 있는 알고리즘을 생각해보자.

알고리즘 생각

1. 경우의 수를 생각해본다. M과 N은 40,000이하이고, 이 둘의 가능한 조합은 16*10^8 = 16억(약 16초) > O(1억=1초) 이므로 시간초과가 나오게 된다. 다른 방법을 생각해봐야한다.=>건너뛰며 해보는 방법!

2. M=5, N=7, <3,6>는 몇번째 해인가? x(3)은 M(5)만큼 반복되는 것을 알 수 있다.

1	<1,1>	6	<1,6>	11	<1,4>	16	<1,2>	21	<1,7>	26	<1,5>	31	<1,3>
2	<2,2>	7	<2,7>	12	<2,5>	17	<2,3>	22	<2,1>	27	<2,6>	32	<2,4>
3	<3,3>	8	<3,1>	13	<3,1>	18	<3,4>	23	<3,2>	28	<3,7>	33	<3,5>
4	<4,4>	9	<4,2>	14	<4,2>	19	<4,5>	24	<4,3>	29	<4,1>	34	<3,6>
5	<5,6>	10	<5,3>	15	<5,3>	20	<5,6>	25	<5,4>	30	<5,2>	35	<5,7>

3. 날짜 계산문제와 마찬가지로, 입력받은 <x,y>를 각각 -1씩 해서 M과 N으로 나눈 나머지를 구하면 된다. 그 나머지+1이 정답이 된다.

0	<0,0>	5	<0,5>	10	<0,3>	15	<0,1>	20	<0,6>	25	<0,4>	30	<0,2>
1	<1,1>	6	<1,6>	11	<1,4>	16	<1,2>	21	<1,0>	26	<1,5>	31	<1,3>
2	<2,2>	7	<2,0>	12	<2,5>	17	<2,3>	22	<2,1>	27	<2,6>	32	<2,4>
3	<3,3>	8	<3,1>	13	<3,6>	18	<3,4>	23	<3,2>	28	<3,0>	33	<3,5>
4	<4,4>	9	<4,2>	14	<4,0>	19	<4,5>	24	<4,3>	29	<4,1>	34	<4,6>

ex) x = 3, y = 2 -> <2,1> : x가 2인 것들을 찾는다. 2인 x에 대해 y의 경우의 수는 n가지가 나온다. i%n == y 인 i를 찾는다.

for (int k=x; k<(n*m); k+=m) {
    if (k%n == y) {
        System.out.println(k+1);
        ok = true;
        break;
    }
}