백준 알고리즘 - 1789번 : 수들의 합

백준 알고리즘 - 1789번 수들의 합 문제입니다.

(참고 - https://www.acmicpc.net/problem/1789 )

코드)

#include <stdio.h>

int main() {

long long int S, i, n=0;

int cnt=0;

scanf("%lld", &S);

for(i=1; ; i++) {

n += i;

cnt++;

if(n > S) {

                        cnt--;

break;

}

}

printf("%d\n", cnt);

return 0;

}

오답 )

#include <stdio.h>

int main() {

long long int S;

int i, n=0, cnt=0;

scanf("%lld", &S);

for(i=1; ; i++) {

n += i;

cnt++;

if(n > S) {

cnt--;

break;

}

}

printf("%d\n", cnt);

return 0;

}

- 정말 흥미로운 문제였습니다. 위에서 오답과 본 코드를 비교해주시기 바랍니다.

무슨 차이가 있는지 발견하셨나요?

로직도 그대로, 변수들의 값들 또한 그대로, 

차이가 있다면 한가지 있습니다.

바로 전 알고리즘 포스팅에서 밝혔었죠. 문제를 유심히 살펴보시라는 말씀을 드렸었습니다.

바로 문제의 조건입니다. 

"첫째 줄에 자연수 S(1≤S≤4,294,967,295)가 주어진다."

그래서 S는 long long int의 값으로 해주었는데?

라고 생각을 하실지 모르겠지만, S뿐만이 아닙니다. 결과값 N을 구해주기 위해 반복문 안에서 루프 조건은

무한루프라는점 입니다. 즉 long long int타입의 S를 만나기 위해서는 i와 n 또한 기본 int형 이상의 값을 필요로 할 수 있으며, 만약 S의 최대값으로 4,294,967,295 라는 값이 입력되었다면 n은 그 이상의 수가 저장됩니다. 

if(n>S)이 이 무한 루프를 끝낼 수 있는 조건이기 때문입니다. 즉 연산과정에서 사용되는 i와 n 또한 long long int타입으로 선언되어져야 시간초과에러를 풀어낼 수 있습니다.

이 부분만 해결하면 나머지는 i를 0부터 차근차근히 더해주어 n에 저장시켜주고, n과 S를 비교하는 단순한 로직이기 때문에 설명은 이정도로 마무리 짓도록 하겠습니다.