푼 날짜 : 2020.11.09
문제링크 : 숫자의 표현
문제 설명
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
문제의 예시와 같습니다.
내 풀이
생각한 풀이를 정리해보았습니다.
임의의 자연수 i 가 있습니다. 이 i 로 n 을 표현해 보겠습니다.
n = i
n = i + (i + 1)
n = i + (i + 1) + (i + 2)
...
이런 식으로 n 을 연속된 i 의 합으로 나타낼 수 있습니다.
그러면 다시 i 입장에서 바라보면,
i = n
i = (n-1)/2
i = (n-1-2)/3
...
으로 나타낼 수 있습니다.
이렇게 표현하고 나니 실마리가 잡혔습니다. 그 당시 메모했던 아이패드 흔적입니다.
i 가 자연수이다 보니 (n - (1부터 k-1 까지의 합)) /k % = 0 인 i 들을 찾을때 마다 카운트를 올려주면 답을 찾을 수 있었습니다.
두 번째 if 문이 카운트를 1을 올려준 후, 실행되기때문에 리턴하기전에 올려준 카운트를 1 빼고 리턴합니다.
두번째 if문을 밖으로 빼면 마지막에 카운트 -1 을 하지 않아도 답을 구할 수 있습니다.
다른사람들 풀이
직관적으로 이해하기가 쉬운 풀이라 생각합니다. 연속된 자연수의 합을 s 라 두고 찾는 풀이라 바로 이해가 됩니다. 하지만 시간복잡도가 O(n²) 으로 num 이 커질수록 시간복잡도가 빠르게 증가합니다.
