[프로그래머스][level2] 숫자의 표현 (C++)

https://programmers.co.kr/learn/courses/30/lessons/12924

코딩테스트 연습 - 숫자의 표현

 

 

 

[난이도] level2
[유형] 구현

[풀이]
n 1개로 무조건 n을 만들 수 있기 때문에 answer의 값은 1부터 시작합니다.
1~n-1을 순회하면서 i+(i+1)+(i+2)... 값을 만들어보면서 n이 넘어가면 break,
n이 나오면 answer에 1을 추가하고 break 하는식으로 답을 구해가면 됩니다.

n이 10000이고 i가 1인 경우에도
1+2+3+4.... = (n*(n+1))/2 = 10000 (등차수열 공식)
을 만족하려면 더하는 횟수인 n이 대충 계산해도 150도 넘을 수 없다는 것을 알 수 있습니다.
그러므로 시간복잡도는 O(10000*150) 정도로 시간내에 해결이 가능합니다.

 

#include <string>
#include <vector>
using namespace std;
int solution(int n) {
    int answer=1;
    for(int i=1;i<n;i++){ 
        bool ok=0;
        int sum=i,cur=i;
        while(sum<n){
            sum+=++cur;
            if(sum==n){
                answer++;
                break;
            }
        }
    }
    return answer;
}

 

 

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/숫자의 표현.cpp