[알고리즘문제] 프로그래머스 - 숫자의 표현

예전에 코테에서 이런 비슷한 문제가 나왔었는데, 당시 멘붕(?)시기여서 못풀었었다. 아마 지금 풀라고 하면 잘 풀 수 있을 것 같다.

 

문제는 간단하다, 자연수 n을 연속된 숫자로 표현할 수 있는 개수를 찾는 문제이다(연산은 +만 사용한다)

예를 들어 15는 1+2+3+4+5, 4+5+6, 7+8, 15로 표현할 수 있다.

 

이 문제는 두가지 방법으로 풀어봤다. 사실 처음에 재귀로 풀었었는데, 효율성 테스트에서 걸려가지고 다른 방법으로 풀었는데 나중에 같은 코드로 다시 채점을 하니 통과가 되었다...

 

1. 재귀

#include <string>
#include <vector>
#include <iostream>

using namespace std;

int count = 0;
int sum = 0;

void recur(int max, int current){
    sum += current;
    if(sum>=max){
        if(sum == max){
            count++;
        }
        return;
    }
    recur(max,current+1);
}

int solution(int n) {
    
    for(int i=1;i<=n;i++){
        recur(n,i);
        sum = 0;
    }
    return count;
}

 

2. 2중 for문

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    
    vector<int> v;
    int answer = 1;
    
    int size = n/2 +1;
    
    for(int i=1;i<=size;i++){
        v.push_back(i);
    }
    
    for(int s=0;s<v.size();s++){
        int sum = 0;
        for(int e=s;e<v.size();e++){
                sum+=v[e];
            if(sum >= n){
                if(sum == n){
                    answer++;
                }
                break;
            }
        }
    }
    

    return answer;
}

생각해보면, 16이라는 숫자가 주어졌을 때, 16의 1/2값인 8부터는 검사할 필요가 없다. 왜냐하면 8이후의 숫자는 무조건 8을 넘으니깐

그래서 for문의 반복횟수는 n/2+1로 했다(+1은 홀수인 경우를 생각). 이렇게 한 이유는 시간복잡도가 n^2이기 때문이다. 근데 나중에 생각해보니 n의 크기가 10,000인데, 1억은 보통 통과가 되기 때문에 굳이 n/2+1을 할 필요는 없을 것 같다.

그리고 어쩃든 n일때는 무조건 1번 가능하기 때문에 answer=1부터 시작한다.