첫번째 풀이 241230
-
4퍼센트에서 시간초과 발생.
-
완전탐색으로 풀었는데, 틀린다. 왜냐하면 n,m이 각각 4만이기 때문에
4 4 100000000 -> 16억의 시간복잡도이기 때문이다.
어떻게 접근해야 할까?
- 문제를 보고 느낀점은 나머지 연산을 생각할 수 있다는 것이다.
왜냐하면 특정 범위 n,m과 동일하다면 다시 1로 세팅된다는 것이다.
- 위의 그대로 하는 것이 아니라 .
1:1 범위 - 10:12 라고 한다면
1번째 해는 1:1
11번째 해는 1:11
10번째 해는 10:10 인데 나머지 처리 되면 표현이 안된다.
그래서 수정하자.
x,y를 0:0 부터 시작하자. 제한값은 10:12
0번째 해는 0:0
9번째 해는 9:9
10번째 해는 0:10
11번째 해는 1:11
12번째 해는 2:0
-
문제와는 링크되지 않지만, 나머지 연산을 통해서 규칙성을 만들었다.
-
현재 내가 푼 시간복잡도는 16억이다. 뭔가 규칙성을 발견해서 시간복잡도는 줄여야 한다.
-
현재 위의 해에 따라서 x;y를 정하고 있는데
규칙성을 찾아야 한다.
횟수를 cnt 라고 하자.
cnt % 10 == wantX 를 찾고 있고,
cnt % 12 == wantY 를 찾고 있다.
-
강의에서 말씀하시는 게
wantX 가 의미하는 것은 cnt 를 m(10) 으로 나눈 나머지를 의미한다. -
즉 im + x = cnt를 의미한다.
하나를 고정해서 cnt를 얻을 수 있다면, y값도 구할 수 있따.
위에서 4만 4만의 시간복잡도가 아닌 4만의 시간복잡도로 접근할 수 있다고 한다.....
결론
: 시작 값에서 특정 end 값까지 진행했다가 다시 시작값으로 돌아와야 한다면 나머지를 사용하자.
🔥🔥🔥