> For the complete documentation index, see [llms.txt](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://heunnajo.gitbook.io/algorithms-problem-solving-skills/brute-force/cain-calendar.md).

# 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를 찾는다.

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