[프로그래머스 4단계] 알고리즘 33. 숫자의 표현

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 33. 숫자의 표현

수학을 공부하던 민지는 재미있는 사실을 발견하였습니다. 그 사실은 바로 연속된 자연수의 합으로 어떤 숫자를 표현하는 방법이 여러 가지라는 것입니다. 예를 들어, 15를 표현하는 방법은

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

로 총 4가지가 존재합니다. 숫자를 입력받아 연속된 수로 표현하는 방법을 반환하는 expressions 함수를 만들어 민지를 도와주세요. 예를 들어 15가 입력된다면 4를 반환해 주면 됩니다.

#include<iostream>

using namespace std;

int expressions(int testCase)

{

    int answer = 0;

    return answer;

}

int main()

{

    int testNo = 15;

    int testAnswer = expressions(testNo);

// 아래는 테스트로 출력해 보기 위한 코드입니다.

    cout<<testAnswer;

}

풀이:

이 문제는 생각보다 쉽게 풀 수 있다. 먼저 몇가지 예를 들어보면서 패턴을 분석해보자. 

testCase = 15

1 + 2 + 3 + 4 + 5

4 + 5 + 6

7 + 8

15

testCase = 6

1 + 2 + 3

6

testCase = 7

3 + 4

7

testCase = 21

1 + 2 + 3 + 4 + 5 + 6

6 + 7 + 8

10 + 11

21

규칙을 찾았는가? 먼저 필자가 찾은 패턴은 다음과 같다.

1. testCase 자기 자신
2. 그 외에는 testCase / 2 + 1의 범위까지만 수를 검사한다.

무슨 말이냐면 21일 경우에는 자신의 반인 10과 그 뒤의 수 11을 더해져서 표현할 수 있다. 그러니까 연속적으로 더해서 수를 표현할 수 있는 범위는 testCase/2 + 1까지라는 소리다. 즉, 1부터 testCase/2 + 1(이하 range)까지 차례대로 누적시켜서 testCase랑 같으면 count를 올려주고 커지면 다음 수를 검사하면 된다. 코드로 보면 간단히 이해가 될 것이다.

  

int expressions(int testCase)

{

    int answer = 1;              //자기 자신

int range = testCase / 2 + 1; //연속된 자연수의 합으로 자신을 표현하려면 범위는

//최대 자신의 반 +1 까지이다. 13 = 6(13/2) + 7(13/2 + 1)

int sum;                      //누적 수

for (int i=1; i<range; i++){ //1~(testCase/2 + 1) 까지 검사

sum = i;                    //검사 처음 수 i

 

for(int j=i+1; j<=range && sum < testCase; j++){    //반복문을 통해 수를 누적 testCase 이상이면 반복문 break    

    sum += j;                                                        

if (sum == testCase)                            //만약 누적수가 testCase와 같다면 counting                

  answer += 1;

}

}

    return answer;

}

이렇게 해서 4단계의 첫 문제를 풀었다! 점점 알고리즘 1일 1문제가 버거워진다...