프로그래머스 - 숫자의 표현 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12924

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

 

 

문제 풀이

n의 범위가 10000 이하의 자연수이므로 브루트포스를 돌리기에 충분하다.

따라서, 차례대로 더해나가며 n을 만들 수 있는지 확인한다.

 

테스트 케이스 1번에서 보면, 1+2+3+...을 더하다보면 15가 만들어진다. 따라서 answer를 ++시켜주고 반복문을 종료한다. 다시, 처음 나오는 수를 증가시켜 2+3+4+...를 하다보면 n을 넘게된다. 더 이상 더하는 것은 의미가 없으므로 반복문을 종료한다. 마찬가지로 3+4+5+... , 4+5+6+... 도 진행해준다.

 

초기화 할 때에는 본인의 수는 항상 포함하므로 1으로 초기화하며 시작하는 숫자는 n/2까지만 증가하면 된다. 왜냐하면 연속되는 수가 n일 때 n/2 + (n/2 + 1) > n이기 때문이다.

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int solution(int n) {
    int answer = 1, start = 1;
    
    while(start <= (n/2)){
        int sum = 0;
        
        for(int i=start; i<n; i++){
            sum += i;
            if(sum > n) break;
            else if(sum == n){
                answer++;
                break;
            }
        }
        start++;
    }
    
    return answer;
}