백준 - 수들의 합(Swift)

백준 - 수들의 합(Swift)

 

 

 문제 설명

 

https://www.acmicpc.net/problem/1789

1789번: 수들의 합

 

 나의 풀이

 

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

 

처음에 이 말을 이해하지 못하고 계속 헛돌았다. N개의 자연수인데 자연수 N의 최댓값을 얼마인지 묻는 것은 결국 개수가 최대가 될 때 몇개인지를 구하는 것이였다.

 

N이 최대개수가 되는 것은 N개의 자연수들을 최대한 다양하게 조합해야한다는 것이다. 즉 1+2+3+4처럼 순서대로 하는 것이 제일 최대가 되게하는 방법인 것이다.

 

예시로 8이라는 숫자가 주어진다면 1부터 계속더해서 1+2+3이 되고 1+2+3+4가 되는 시점에는 8을 넘어서게 된다. 그래서 4가지의 경우보다 작은 3가지의 경우로 8을 만드려면 1+2+5가 되고 결국 3가지가 답이 된다.

 

그래서 sum을 1부터 계속 더하면서 구한 값보다 같거나 커지는 시점이 N이 최대가 되는 시점이다.

 

import Foundation

let n = Int(readLine()!)!
var sum = 0
var idx = 1
var cnt = 0
while sum < n {
    sum += idx
    idx += 1
    cnt += 1
}
if sum == n {
    print(cnt)
} else {
    print(cnt-1)
}