Link : Lv2. 숫자의 표현
- 문제 설명
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 이하의 자연수 입니다.
- 문제 풀이
연속된 숫자들의 합에서 연속된 숫자의 시작 숫자는 특정 숫자의 반에 걸치거나 넘지 않을 것이다.
이유는 15를 기준으로 보면 된다. 반은 7 이며 (소수점 버림) 다음 숫자인 8을 더하면 15이다.
16을 보면 반은 8이며 다음 숫자인 9를 더하면 17이 되므로 8 + 9는 이뤄지지 않는다.
그러면 자기 자신만 있는 경우를 제외하고는 1부터 숫자의 반까지만 반복문을 돌리면 되겠다.
15인 경우를 예로 다시 들어보면,
15의 반 이내인 7이하 숫자(i, j) i 부터 시작해서 j 번 까지의 연속된 숫자의 합을 수식으로 나타내면
i, i + 1, i + 2 … i + (j – 1) 이며 분리하면 .. (i + i + i .. (j번 반복)) + (1 + 2 + .. + (j – 1)) 이다.
이를 수식으로 나타내면 i 가 j번 나타나므로 i * j 이며
나머지는 1 + 2 + … (j – 1) 이므로 (j – 1) * j / 2 일 것이다.
합치면 i * j + (j – 1) * j / 2 가 될 것이다.
즉, i 가 1이라면 1 + 2 + 3 + 4 + 5 j가 5인 경우가 15가 된다.
1부터 특정 숫자 반까지 탐색하나 각 숫자 마다 연속된 숫자의 합을 구하는 완전 탐색이므로
효율이 그리 좋지는 않다. 더 좋은 효율이 있을 것 같긴 한데 잘 생각이 나지는 않는다.
이런식으로 구하면 BigO(n ^ 2) 일 것이다. (실제로는 그 정도 까지는 가지 않을 것이다)
Source Code : representation_numbers.cpp