[백준] 수들의 합

1.  문제

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

 

2. 핵심요약

■ 문제유형 : 탐욕(Greedy) 알고리즘

■ S: 자연수의 합 (문제의 Input)

■ N: 합계 S가 성립하는 자연수들의 최대 갯수

 

3. 문제풀이 접근

■ 최대한 많은 숫자를 이용하여 합계 S를 만들기 위해서는 가장 작은값(1)부터 차례대로 더해 나가야 한다.

■ 그 다음 더해지는 숫자를 고려하여 더해지는 값이 S 보다 더 크게 될때까지 카운트한다.

 

4. 파이썬 코딩

isTest = True
if isTest:
    f = open("./1789.txt", 'r')
    s = int(f.readline())
else:
    s = int(input())
 
current = 0
cnt = 0
 
adder = 1
 
while (s >= current):
    current += adder
 
    adder += 1
    cnt += 1
 
    if adder > s - current:
        break
 
print(cnt)

 

 

5. JavaScript 코딩

let isTest = true
 
let fs = require('fs');
let input;
if (isTest) {
    input = fs.readFileSync('./1789.txt').toString().split('\n');
} else {
    input = fs.readFileSync('/dev/stdin').toString().split('\n');
}
 
s = parseInt(input[0]);
 
current = 0
cnt = 0;
 
adder = 1;
 
while (s >= current) {
    current += adder;
    console.log(current);
 
    adder++;
    cnt++;
 
    if (adder > s - current) {
        break;
    }
}
 
console.log(cnt);