1789번. 수들의 합

문제 분석

a+b+c+....z = s가 되는 자연수 n의 개수를 구한다.

이때  a,b,c 들은 서로 다른 자연수들이고, 이 자연수들의 개수는 1부터 하나씩 더해주어야 최대가 된다. 

 

1+2+3=6 의 예시를 이용해서 반복문으로 i의 값을 1씩 늘려가면서 6(자연수의합)과 같아지는 경우 나오도록 설정했다. 

 

알고리즘 설계

우선 s의 최댓값이 위의 그림에 나와있듯이 매우 크므로, long long 자료형으로 설정한다.

sum도 마찬가지로!

 

이후에 while문으로 1부터 계속해서 더한 값이 sum보다 클 때까지 반복한다.

이때 i는 1로 초기값을 설정하고 i++해준다.

만약 sum > s 라면 i값을 하나 빼주고 break문으로 반복문을 탈출해서 i값을 출력한다.

 

시간 복잡도

sum을 구할 때까지 while문을 반복하므로 n번 -> o(n) 

 

코드

#include <iostream>
using namespace std;
/*
1. 자연수의 합을 입력받는다
2. 자연수 개수 n의 최대값을 찾는다
3. n을 출력한다
*/
int main() {
    //1
    long long s;
    cin >> s;
    //2
    long long sum = 0, i = 1;

    while (1) {              
        sum = sum + i;      
        if (sum > s) {
            i--;
            break;
        }
        i++;
    }

    cout << i << '\n';
    return 0;

}

 

느낀 점

우선 문제에서 최댓값이 명시되어 있는 경우, 그에 맞는 자료형(int, long, long lonig)을 써야 오류가 안 난다..

나는 항상 int형으로 쓰는 게 익숙해서 매번 쓰고나서 틀리고 그때서야 확인하는데 자료형의 최댓값에 관해서 다시 공부하고 앞으로는 적절한 자료형으로 초기설정을 하는 습관을 들여야겠다.

 

둘째로는 이렇게 while문이나 for문으로 반복하는 문제에서 1차이로 정답을 못 맞춘 경우가 많은데 아직 반복문에 완벽하게 학습이 안된 것 같다. ㅠㅠ 이 부분도 보완하도록 해야겠다.