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

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

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

입력값의 최대가 10,000 이므로 O(N^2) 풀이로는 시간초과가 발생할 위험이 있으므로 투 포인터를 이용하여 O(N)의 시간 복잡도로 해결했습니다.

 

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

int solution(int n) {
    int answer = 0, head = 0, tail = 0, sum = 0;
    vector<int> v(n);
    
    for(int i = 0; i < n; i++) {
        v[i] = i + 1;
    }
    
    while(1) {
        if(sum > n) sum -= v[head++];
        else if(tail == n) break;
        else sum += v[tail++];
        if(sum == n) answer++;
    }
    
    return answer;
}