[c++] 프로그래머스 - 숫자의 표현(Level 2)

문제

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

코드

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
    int answer = 0;
    
    for(int i=1; i<=n; i++){
        int sum = 0;
        for(int k=i; k<=n; k++){
            sum+=k;
            if(sum>n) break;
            else if(sum == n){
                answer++;
                break;
            }
        }
    }
    return answer;
}

풀이(18분)

처음에 문제를 딱 보았을 때 입력값이 n의 최댓값이 10000이길래 DP로 접근해볼까 했지만 DP 테이블이 도저히 만들어지지 않을 것 같아 완전 탐색으로 한번 고민했습니다.
이중 포문에 n까지 도니까 o(n^2)이라서 시간 초과가 뜰거라 생각할 수도 있지만 잘 생각해보면 1~141까지의 누적합이 10011이므로 사실상 시간 복잡도는 O(10000*141)이 됩니다. 따라서 완전 탐색으로 무난하게 풀 수 있는 문제였습니다.