프로그래머스 | 숫자의 표현 [파이썬 python]

프로그래머스

 

코드

def solution(n):
    answer = 0  # 연속된 자연수로 n을 표현하는 방법의 수
    for i in range(1, n+1):
        hap = 0
        
        # hap이 n보다 크거나 같아질 때까지 i부터 순차적으로 더함
        while hap < n:
            hap += i
            i += 1
        if hap == n: # 만약 hap이 n과 같으면 연속된 자연수로 나타낼 수 있으므로 방법 +1
            answer += 1
            
    return answer

자연수 n을 연속된 자연수로 표현할 수 있는 가짓수를 구하는 문제이다.

예를 들어, n=15이면 다음과 같은 4가지 방법으로 나타낼 수 있다.

• 15
• 7 + 8
• 4 + 5 + 6
• 1+ 2 + 3 + 4+ 5

 

어떻게 이 문제를 풀어가야 할지 1부터 15까지의 수를 모두 직접 써가며 개수를 세보았지만 특별한 규칙이 보이지 않았다.

그래서 할 수 없이 1부터 계속해서 더해보는 방법으로 코드를 작성하게 되었다.

for i in range(1, n+1):
    hap = 0

    # hap이 n보다 크거나 같아질 때까지 i부터 순차적으로 더함
    while hap < n:
        hap += i
        i += 1
    if hap == n:
    	answer += 1

i=1이면 while문에서는 hap에 1부터 계속해서 수를 더해나가고, i=2이면 2부터 더해나가는 것이다.

hap이 n보다 작으면 과정을 계속해서 반복하고 크거나 같아지면 while문은 실행하지 않는다.

while문을 탈출했을 때, hap == n이면 연속된 수로 n을 만들 수 있는 것이므로 answer에 +1을 해준다.

 

이렇게 모든 경우의 수를 탐색해야만 하는 것인지 고민하게 되었는데 시간초과 없이 정답으로 인정되어서 신기했다.

하지만 다른 사람들의 풀이를 보니 n의 약수 중 홀수의 개수가 구하고자 하는 답과 같다는 것을 알게 되었다.

 

다른 사람의 코드

def solution(n):
    return len([i for i in range(1, n+1, 2) if n % i is 0])

어째서 홀수인 약수의 개수가 답이 될 수 있는 것인지 알고 싶어서 많은 풀이들을 찾아보았다.

그 결과, 이 문제는 수학 문제를 코드로 나타내는 문제였다.. 수학까지 생각해야 문제를 풀 수 있다니

 

n 이하의 숫자 a부터 k개의 숫자의 합이 n이라고 가정할 때, $a = \frac{n}{k} + \frac {1-k}{2}$ 가 된다.

이 식을 통해 a를 자연수로 만들기 위한 k의 조건은 k는 n의 약수이고 홀수이어야만 하는 것을 알 수 있다.

n의 약수이면서 홀수인 k의 개수만큼 연속된 자연수로 합을 만들 수 있다.

더 자세한 증명은 아래 풀이를 참고하길 바란다.

숫자의 표현