[Programmers] 숫자의 표현

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

댓글 남기기