프로그래머스] C++ 연습문제 - 숫자의 표현(level 2)

해당 문제는 프로그래머스 코딩테스트 연습에 있는 문제입니다.

아래 링크를 통해 풀 수 있습니다.

 

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

 

 

 

1. 문제

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

• 1 + 2 + 3 + 4 + 5 = 15
• 4 + 5 + 6 = 15
• 7 + 8 = 15
• 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항

• n은 10,000 이하의 자연수 입니다.

---

입출력 예

n	result
15	4

입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

 

 

2. 조건

1. 연속되는 자연수의 합 중 주어진 n 값과 일치하는 합의 갯수를 구하여라.

2. 연속되지 않는 ex) 1, 3, 7 는 제외한다.

 

3. 풀이

이 문제를 예전에 봤을 때 어떻게 풀까 생각하다가 귀찮아서 넘어갔던 문제입니다.

그때 당시에 queue를 이용해 재귀적으로 풀까 생각했던 기억이 있는데 이번에도 똑같은 생각을 했습니다.

 

하지만 연속된 자연수이고 숫자가 반복되는걸 보고 굳이!! 복잡하게할 필요가 없다고 생각해서 다음과 같이 풀었습니다.

 

1. 최대 반복지점을 정합니다.

여기서 최대 반복지점이란??

저희는 연속되는 자연수의 합중 n값과 일치하는 값을 구해야 합니다.

결과적으로 n / 2 이상 더하면 의미가 없다는 뜻입니다.

ex) n = 50 이라면 n / 2 = 25. 25 + 26 = 51 이 되므로 의미가 없다.

 

2. (1 ~ n / 2) 을 더했을 때 n값보다 크거나 같을 때 까지 계속 더해줍니다.

왜냐하면 연속된 자연수의 합을 구해야 하기 때문입니다.

 

3. (1 ~ n / 2) 을 더했을 때 n값보다 크다면 역으로 1부터 차례대로 빼줍니다.

문제의 예시를 보면 아시겠지만 1 ~ 5 까지 더한 후 4 ~ 6 을 더합니다.

4 ~ 6 에는 1, 2, 3 이 빠져있죠.

이를통해 알 수 있는 사실은 차례대로 더한 값이 더 크다면 더했던 숫자를 차례대로 빼면서 숫자의 균형을 맞춰주면 되는 것입니다.

 

4. n이 홀수일 경우 (n + 1) / 2 를 해준다.

15와 같은 경우 7 + 8 = 15 입니다.

하지만 15 / 2 = 7 이 되죠.

8이라는 숫자까지 코드상 반복되지 않으므로 + 1을 해줘서 균형을 맞춰줍니다.

 

4. 코드

using namespace std;

int solution(int n) {

    int num = (n + 1) / 2;

    int sum = 0, answer = 1, j = 1;

    

    for(int i = 1; i <= num; i++){

        sum += i;

        if(sum >= n){

            while(sum > n) sum -= j++;

            if(sum == n) answer++;

        }

    }

    

    return n != 1 ? answer : 1;

}

 

 

 

오랜만에 풀어봤네요.