프로그래머스, 숫자의 표현 : C++ [CPP]

음.. 그냥 생각나는대로 

했지만 n^2의 알고리즘은 너무 혐오스럽길래... 과연 이렇게 짜도 되나생각했다.

 

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

 

---

 

#맞는 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    //1부터 시작O(n)
    for(int i = 1; i<n; i++){
        int res = i;
        //O(n/2) -> 하지만 j가 n/2에 가까울수록 이 루프가 실행되는 빈도가 줄어듬
        while(1){
            for(int j = i+1; j<n; j++){
                res += j;
                //더했을 때 넘치거나 같으면 우선 종료
                if(res >= n){
                    break;
                }
            }
            //종료후 같은지 넘친지 조사
            if(res == n) answer++;
            else break;
        }
    }
    
    //n은 무조건 n하나로 된다.
    answer++;
    
    
    return answer;
}

 

생각해봤는데

j가 n/2를 넘지 않는다.

즉, 약 n/2개의 원소만 2번 조사한다...

n^2/4라고나 할까..?

 

그랬더니 효율성도 통과하더이다.