프로그래머스 Lv2 숫자의 표현

 

문제의 접근을
먼저 N이 될 수 있는 수를 만들고
그 다음 수가 오면 그 다음 수만큼 배열에서 값을 뺀다.
만약에 다음에 오는 수보다 뺀 값이 크다면 다시 다음 수를 빼고 다음수를 추가한다.
따라서 재귀를 사용해서 문제를 해결하면 될 것 같다.

첫번째로 N만큼의 배열을 만든다.
두번째로 N만큼의 배열에서 다음 수 만큼 뺀다.
세번째로 뺀 수가 다음 수 보다 크다면 앞의 수를 빼고 다음 수를 추가한다.
라고 접근하고 풀이했다.

sum이 n보다 작거나 같다면 deque에 원소를 더했다.
sum이 n보다 크다면 deque의 원소를 뺐다.
sum이 n과 같은 경우는 answer를 증가했다.
deque의 마지막 값이 n과 같다면 반복문을 종료 시켰다.

#include <string>
#include <vector>
#include <deque>

using namespace std;

int solution(int n) 
{
    int answer = 0;
    deque<int> deq;
    int i = 1;
    int sum = 0;
    
    while(1)
    {
        
        if(sum == n)
        {
            ++answer;
            
            if(deq.back() == n)
                return answer;
            
            deq.push_back(i);
            sum += deq.back();
            ++i;
        }else if(sum > n)
        {
            sum -= deq.front();
            deq.pop_front();
        }else
        {
            deq.push_back(i);
            sum += deq.back();
            ++i;
        }
    }
    
    
    return answer;
}

 

다른 사람의 풀이를 보니 1부터 n / 2까지 검사했다.

1 + 2 + 3 + 4 + 5 = 15	(answer = 1)
2 + 3 + 4 + 5 + 6  > 15
3 + 4 + 5 + 6 > 15
4 + 5 +6 = 15	(answer = 2)
5 + 6 + 7 > 15
6 + 7 + 8 > 15
7 + 8 = 15	(answer = 3)

1부터 n까지의 합을 구하는데 sum == n이면 정답을 늘리고,
sum < n 이면 sum을 키우고,
sun >n이면 반복문을 종료하는 식으로 풀었다.
그리고 sum에 자기 자신을 무조건 포함 되므로 정답에 포함시켰다.

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;

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