[백준]1011-Fly me to the Alpha Centauri
이번 문제는 1011번 Fly...여튼 문제이다.
정답 비율이 27퍼센트밖에 되지 않아 걱정을 많이 했는데, 물론 좀 힘들긴 했지만 막 하루종일 고민하고 그런 정도는 아니었다.
일단 문제를 읽은 후 메모장으로 정리를 해봤다.
행성간의 거리가 1일 경우에는 1번, 2일 경우에는 2번, 3일 경우에는 3번..
1 -> 1
2 -> 2
3 -> 3
4 -> 3
5 -> 4
6 -> 4
7 -> 5
8 -> 5
9 -> 5
10 -> 6
11 -> 6
12 -> 6
13 -> 7
14 -> 7
15 -> 7
16 -> 7
17 -> 8
18 -> 8
19 -> 8
20 -> 8
21
22
23
24
25 -> 9
위와 같은 방식으로 작동 횟수가 늘어나는 것을 알아냈다.
대충 보면 아무 규칙이 없는 것 같은데, 자세히 보면 규칙이 숨어있다.
그러기 전에 이 문제를 딱 보고 가장 먼저 생각나는 경우의 수를 생각해보자.
1 -> 2 -> 3 -> 2 -> 1 X(3) = 9
또는
1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 X(4) = 16
위와 같이 속도가 1씩 늘어나고 1씩 줄어드는 경우가 가장 먼저 생각 날 것이다. (편의를 위해 위와 같은 경우를 X(a)경우라고 하자.)
이런 숫자들을 더한 값을 나열해보면..
1 4 9 16 25...
위에 나열해 놓은 숫자 중에서 굵은 글씨로 해놓은 숫자들이다.
X경우 후로는 숫자가 1씩 무조건 증가한다.
또한, X(a)의 경우 X(a) - (a - 1) 에서 X(a)까지 a가지의 길이에 대하여 a*2 - 1이 최소한의 작동 회수이고,
X(a) + 1 에서 X(a) + a까지 a가지 길이에 대하여 a*2이 최소한의 작동 회수이다.
좀 더 개념적으로 표현하자면,
위와 같이 표현된다는 것이다.
그래서 이걸 이용해서 코드를 짜면..
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #include <stdio.h> int pz(int num); int main() { int T; unsigned int x, y; scanf("%d", &T); unsigned int sub; unsigned int n1; unsigned int n2; int j; for (int i = 0; i < T; i++) { scanf("%u %u", &x, &y); sub = y - x; n1 = 0; n2 = 0; for (j = 1; n1 < sub; j += 2) { n2 = n1; n1 = pz(j); } printf("%d\n", n1 - sub > sub - n2 ? j - 3 : j - 2); } return 0; } int pz(int num) { int sum = 0; for (int i = 0; i <= num / 2; i++) sum += 2 * i; sum += num / 2 + 1; return sum; } | cs |
허허.. 시간초과..
제한시간이 2초라는데 왜그럴까.. 하며 좀 큰 길이를 넣어보니.. 확실히 체감되도록 느리더군요 허허..
그래서 다른 방식을 찾아보는데..
"X(a)의 경우에 a*2-1이 최소한의 경우의 수이고, 최소 횟수가 나열된 것을 보면 1과 2가 1번, 3과 4가 2번, 5와 6이 3번.. 이런 식으로 되는데 이걸 이용할 수 있지 않을까?"
그래서 나온 코드가
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <stdio.h> int main() { int T; unsigned int x, y; scanf("%d", &T); unsigned int sub; unsigned int n1; unsigned int n2; int j; for (int i = 0; i < T; i++) { scanf("%u %u", &x, &y); sub = y - x; n1 = 0; n2 = 0; j = 0; while (n1 < sub) { n2 += j * 2; n1 += ++j * 2; } printf("%d\n", n1 - sub < j ? j * 2 : j * 2 - 1); } return 0; } | cs |
코드에 대한 해석은.. 뭐 해봤자 잡다한거 빼면 20줄도 안되니.. 스스로 생각하는 시간을 가지시길..ㅎㅎ