잘못 구현한 에라토스테네스의 체
첨엔 거지같이 풀어서 다른 분의 깔삼한 코드에 감명받아 여기에 옮기고자 한다.
cubelover님 감사합니다 ㅜㅜ
N = 12 인 경우에 답은 41인데, 과정을 표로 그려보면 다음과 같다.
| i | j | |||||||||||||
| 1 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | = | 12회 |
| 2 | 1 | 3 | 5 | 7 | 9 | 11 | = | 6회 | ||||||
| 3 | 1 | 4 | 7 | 10 | = | 4회 | ||||||||
| … | = | |||||||||||||
| 5 | 1 | 6 | 11 | = | 3회 | |||||||||
| … | = | |||||||||||||
| 11 | 1 | 12 | = | 2회 | ||||||||||
| 12 | 1 | = | 1회 | |||||||||||
| 총 | 41회 |
아래서 부터 과정을 살펴보면,
1부터 12칸씩 뛰는데 한번도 나아갈 수 없다.
1부터 11칸씩 뛰는데 한번만 나아갈 수 있다.
...
횟수에 초점을 맞춰보면, 약수처럼 횟수가 늘어남을 알 수 있다. 따라서 횟수들의 종류 사이마다 i가 몇개씩 있는지만 알면,
n의 약수 갯수와 비스무리한 시간에 풀릴 것이다!
밑에서 부터 간격을 점프해보자.
1부터 시작하므로 최대 점프길이는 11이다. 11/12 = 0 이고, 1을 더하면 1회가 계산된다.
다음 i를 계산하는데는 직관적으로 계산된다. 11 / 1회 = 11이므로 다음 i는 11이다.
이는 1회 = 1번 점프 = 1부터 11까지 최대한 멀리 점프할수 있는 수 = 11 같이 이해하면 될 것 같다.
i = 11일 때 j는 두 번 등장한다. = 2회
다음 i = 11 / 2회 = 5이다.
즉 횟수가 달라지는 i들은(횟수들의 최대 i값들은) 12->11->5->3->2->1 순이다.
점프 횟수와 i들의 간격도 모두 구할 수 있으니 다음 처럼 간단한 코드로 풀이가 마무리된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #include <cstdio> long long ans; int n; int main() { scanf("%d", &n); n--; for (int i = n + 1; i != 0; i = n / ((n / i) + 1)) ans += (n / i + 1) * (i - (n / ((n / i) + 1))); printf("%lld\n", ans); } | cs |