1부터 더해가면서 sum > s가 되는 순간 마지막으로 더한 숫자를 p라 하고,
sum < s를 만족하는 최대의 sum을 sum2라 합시다.
sum2 == 1 + 2 +...+ p-1 < s
sum2 + p > s 이므로 s의 최대값은 sum2 + p - 1 입니다.
이때, sum2에 더해진 1부터 p-1 까지의 수들을 큰 수 부터 1씩 증가시키면 더해진 숫자들은 겹치지 않고, sum2가 1씩 증가하게 됩니다.
이렇게 숫자들이 겹치지 않게 sum + 1부터 sum + (p-1)까지의 수를 구할 수 있습니다.
d252b 6년 전
예를 들어, 어떤 수 S가 들어오고,
최대의 N을 위해 당연히 1부터(가장 작은 수부터) 빼는 건 이해가 되는데요.
1+2+3+... n-1 + n + n+1 .. 이런식으로 쭉쭉 갈 때,
위의 수열의 총 합을 Sum 이라고 하면,
Sum<S 인경우 (이것은 논외로 치고 ; Sum에 어떤 숫자를 더 더해야 하므로)
Sum==S 인 경우 (이것은 딱 정확한 갯수)
Sum > S인 경우 ( <- 이렇게 S를 넘겼을 경우, Sum, 즉, 1부터 N까지의 총합이 S를 넘는 경우, 그 N개의 갯수를 이용해서 정확히
S와 같은 Sum을 만들 수 있다는 보장이 있나요??
예를 들어 7을 보면
1+2+3 = 6
1+2+3+4 = 10
이므로 S=7 일때, N은 3 인데요.
이 때, S가 10보다 작으므로 (즉, N이 4보다는 작다) 이것까지는 이해가 됩니다.
그러나 S가 3개짜리를 이용해서 딱 7을 만들 수 있다는 보장이 있나요?