[프로그래머스] 숫자의 표현 수학적 풀이 및 증명

문제 해석

---

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 이하의 자연수 입니다

---

문제 풀이

---

[풀이 1번: 투포인터]

숫자 1만까지를 1부터 N까지 합이 1만일 때, 2부터 N까지 합이 1만일 때... 모든 경우를 찾는 코드를 처음에 생각해냈다.시간이 너무 길어질 것 같아서 꼼수를 생각해냈다.

1. 처음 합이 N인 경우부터 투포인터를 이용하여 크다면 가장 작은 수를 버리고 작다면 이어지는 큰 수를 취한다.
2. N이라는 숫자가 주어진다면 처음합은 N/2까지만 찾아내도 되는데 N/2을 a로 두었을 때
   (a까지의 부분합은 a(a+1)/2일 것이고 이것이 N보다 큰 경우를 계산하면 (N-3)²/8 > 9/8로 N이 6일 때부터는 성립한다.)
3. 만약 2번에서 찾지 못한다면 시작점과 끝점을 0으로 시작한다.

[풀이 2번: 수학]

이 풀이를 처음보고 경악을 금치 못했다. 머리로 생각해내지 못하고 코드를 보고 알아낸 풀이다. 처음 생각한 사람 대단한 사람...
정말 증명하는데만 2시간 걸린 것 같은데 나는 수학과 머리는 아닌 것 같다 ㅎㅎ.

 

1. 자연수 k부터 m개의 연속된 숫자로 n을 나타낸다고 하면 아래와 같은 수식을 이용할 수 있다.
(m이 홀수나 짝수인 경우 모두 짝수와 홀수의 곱으로 나타나게 된다)

 

2. 여기서 2N이 홀수와 짝수의 곱으로 표현되려면 N의 홀수 약수의 갯수를 찾아내면 되는 문제가 된다.

 

---

코   드

---

투포인터 풀이

투포인터 풀이

#include <string>
#include <vector>
using namespace std;

int solution(int n) {
    int answer = 1, ep = 0, sum = 0, sp = 1;
    
    for (int i = 0 ; i < n/2; i++) {
        if (i * (i + 1) / 2 >= n) {
            ep = i;
            sum = i * (i + 1) / 2;
            break;
        }
    }
    
    while (ep != n) {
        if (sum == n) {
            answer++;
            sum -= sp;
            sp++;
        }
        else if(sum > n) {
            sum -= sp;
            sp++;
        }
        else {
            ep++;
            sum += ep;
        }
    }
    
    return answer;
}

수학적 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    for (int i = 1 ; i <= n ; i+=2) {
        if (n % i == 0) {
            answer++;
        }
    }
    
    return answer;
}

---

느낀점: 중등 수학이 이렇게 쓰일 줄 몰랐다... 코드를 효율적으로 짜려면 수학이나 정수론을 다시 공부해야하는가 싶은 하루였다.

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

프로그래머스