[ 프로그래머스 ] 숫자의 표현

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/12924

풀이

---

연속된 자연수로 숫자를 표현할 때, 연속된 숫자를 작은 값부터 하나하나 더해보면 정답이 나온다.

#include <string>
#include <vector>

using namespace std;

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

    for (int i = 0; i < n; i++)
    {
        sum = 0;

        for (int j = i+1; j <= n; j++)
        {
            sum += j;

            if (sum == n)
            {
                answer++;
                break;
            }

            else if (sum > n)
            {
                break;
            }
        }
    }

    return answer;
}

※ 다른 코드

이를 더 효율적으로 풀자면, 연속된 자연수로 자기 자신을 표현할 수 있는 방법 중 자기 자신을 제외하면 최대로 사용할 수 있는 원소는 자신 / 2 + 1 값이다. 이를 통해 탐색 시, 기존보다 더 적은 탐색 수로 정답을 찾을 수 있다.

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

using namespace std;

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