연속된 수의 합으로 특정 수를 만들 수 있는 경우의 수

Programmers Lv.2 '숫자의 표현' 문제를 풀다가 정말 간단한 풀이가 보여서, 관련 개념을 정리하려고 한다.

 

문제는 다음과 같다.

15라는 숫자가 주어지면, 15를 만들 수 있는 연속된 수의 합의 경우의 수들을 반환하면 된다.

 

ex)
number : 15

1 + 2 + 3 + 4 + 5 = 15    - 1️⃣
4 + 5 + 6 = 15               - 2️⃣
7 + 8 = 15                    - 3️⃣
15 = 15                        - 4️⃣

총 경우의 수 4가지로 4를 반환

 

내가 작성해서 제출했던 풀이는 다음과 같다.

 

 

주어진 숫자까지 반복문을 돌고, 그 내부에서 또 임시의 i를 만들어서 연속된 수의 합이 주어진 숫자가 되는 경우를 찾는 방법을 사용했다.

 

주어진 숫자가 15라고 가정하면,

tempI는 1부터 5까지 더해질 것이고, 주어진 숫자와 같기 때문에 while문을 빠져나와 i가 2인 경우의 for문을 돌기 시작한다.

다시 tempI는 2가 될 것이고, while문 안에서 연속된 수를 더하다가 주어진 숫자 15보다 크기 때문에 아무런 결과 없이 while문을 빠져 나오고 i가 3인 for문을 돌기 시작한다.

내가 푼 풀이는 이러한 과정을 반복한다.

 

 

다른 사람의 풀이를 확인하니 정말 간단한 풀이였고, 시간 복잡도나 효율성 측면에서 아주 좋았다.

풀이는 다음과 같았다.

 

 

1부터 주어진 숫자까지 2씩 더하면서, 주어진 숫자와 나눈 나머지가 0일 때, 경우의 수는 1씩 증가한다.

처음엔 이해가 안되었고, 관련 수학 이론이 있나 생각이 들었다.

 

결론은 다음과 같은 정수론 정리가 있다는 것이다.

 

특정 숫자를 연속된 수의 합으로 표현할 수 있는 경우의 수는

그 특정 숫자의 약수 중 홀수 약수의 개수와 같다.

 

ex) number : 15  → 1, 3, 5, 15   총 4개

 

 

추후에 알고리즘 문제를 풀면서 이런 개념을 적용할 부분이 종종 있을 것 같고, 이 방법을 사용해서 쉽게 풀어낼 수 있을 것 같다.