[백준/Swift] 1789: 수들의 합 | PS일지

문제

간단한 문제 요약

서로 다른 N 개의 자연수의 합이 S일 때, 자연수 N의 최대 값은 얼마일까?

문제 풀이

최대한 많이 서로 다른 자연수를 더해주어 S를 만들어야 합니다. 가장 작은 자연수 1부터 더해가는게 최대한 많은 서로다른 N개의 자연수를 사용할 수 있습니다.

 

이때 이전 자연수들의 덧셈 + 특정 자연수를 더한 값이 S라면, 서로 다른 자연수는 특정 자연수 개수만큼 존재합니다.

예를들어 S = 3이고

자연수의 덧셈이 1부터 시작한다면,

1.

1+2 = 3

답은 2입니다. 

 

만약 특정 자연수의 덧셈이 S를 초과한다면, 초과한 값 - S를 한 자연수만 빼면 됩니다. 그럼으로 특정 자연수 -1이 답입니다.

예를들어 S = 5이고,

자연수의 덧셈은 1부터 시작합니다.

1 + 2 = 3

3 + 3 = 6

이땐 S를 초과함으로 6 - S를 한 자연수 한개만 빼면 S를 만들 수 있다는 사실..

 

다시 첫번째 예시에서, 1 + 2 = 3입니다. 여기서 3을 더한다면, 6이되고, S인 3을 초과하게 됩니다. 그럼 결국 6 - 3 을 한 자연수를 뺀 경우가 답이 된다는 사실..

코드

_={
  var i = 0, n = Int(readLine()!)!
  (1..<4294967295).reduce(0){
    i+=1
    if $0+$1>n { print(i-1);exit(0); }
    return $0+$1
  }
}()

 

 

여기서 (1...n) 까지의 덧셈 공식은 n*(n+1)/2 입니다.

이 공식을 활용해 S를 초과할 때까지 더한 n을 찾고 -1을 입력해도 됩니다.

var s = Int(readLine()!)!, n = 1
while n*(n+1)/2<=s { n+=1 }
print(n-1)