[알고리즘/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)