[알고리즘/Swift] 1789 수들의 합

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1789 수들의 합
• 제출 언어: Swift
• 알고리즘 분류:
  • 수학
  • 그리디 이론

---

풀이

그리디 이론

그리디 이론에 대한 설명은 그리디 알고리즘에 정리해놨으므로 생략하겠다
복잡하게 생각하지 않고 단순하게 while문을 사용하여 구현하니 쉽게 해결이 되었다

알고리즘 설계

• 해 선택 : N이 최대가 되려면 그 서로 다른 자연수들의 값이 최소가 되어야 하므로 1부터 커지는 방향으로 해 집합에 추가한다
• 실행 가능성 검사 : 해 집합에 있는 해들의 합이 S를 넘는지 확인한다
• 해 검사 : 해 집합에 하나의 해를 추가했을 때 S를 넘을 경우, 알고리즘을 종료하고 해의 개수를 count한다

이러한 알고리즘을 바탕으로 다음과 같은 코드를 짰다

• 합이 S가 되는 서로 다른 자연수 N개가 있을 때 N이 최대가 되게 하려면 그 서로 다른 자연수들의 값이 최소가 되어야 할 것이다
• 그러므로 1부터 증가하면서 임시적인 값인 temp에 더해주었고, 더할 때마다그 때의 개수를 count 해줬다
• 마지막으로 temp의 값이 S를 넘기자마자 count한 자연수의 개수를 출력하고 break해서 while문을 빠져나온다 (이때 break를 해주지 않으면 시간초과가 걸릴 수 있음)
• 물론 temp가 S를 넘겼을 때의 숫자 count를 해주면 안된다

---

전체 코드

import Foundation

var S = Int(readLine()!)!
var N = 0
var temp = 0
for i in 1...S{
    temp += i
    N += 1
    if temp > S{
        N -= 1
        break
    }
}
print(N)