백준 11659
-
[알고리즘][백준] 11659. 구간 합 구하기 4알고리즘 2024. 4. 27. 10:22
문제https://www.acmicpc.net/problem/11659 문제 아이디어숫자가 100000개, 케이스가 100000개 이므로 한 케이스 당 한 사이클의 개수를 더하면 시간 초과가 날 것입니다. 따라서 말 그대로 구간 합을 구해나가면 됩니다. 5 4 3 2 1 이 있다고 한다면, 아래와 같이 구할 수 있습니다.1번째까지의 합: 5 = 52번째까지의 합: 5 + 4 = 93번째까지의 합: 5 + 4 + 3 = 124번째까지의 합: 5 + 4 + 3 + 2 = 145번째가지의 합: 5 + 4 + 3+ 2 + 1 = 15 그렇다면 이제 아래와 같이 생각할 수 있습니다.2번째부터 4번째까지의 합: 4번째까지의 합 - 1번째까지의 합 (2번, 3번, 4번의 수를 더하는 것이므로 4번까지 다 더한 다음에..