d252b   2년 전

예를 들어, 어떤 수 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을 만들 수 있다는 보장이 있나요?

degurii   2년 전

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   2년 전

오!! 감사합니다. 완전 이해 되었습니다!!!

많은 도움이 되었습니다.

여기서 같은 동아리 분의 도움을 받게 되네요 ㅋㅋㅋ 


댓글을 작성하려면 로그인해야 합니다.