[Python] 프로그래머스 level 2. 숫자의 표현

 

문제 접근

1~n 까지의 합(sum)에 사용된 자연수-> 나올 수 있는 방법의 수를 구하면 됨

 

코드

def solution(n):
    answer = 0
    for i in range(1, n+1): # 1~n
        sum = 0
        for j in range(i,n+1): # i~n
            sum += j # n까지 더한다
            if sum == n: # n이 되면
                answer += 1 # 방벙의 수 +
                break # 멈춘다
            elif sum > n: 
                break 
    return answer #자연수 개수

 

공식을 이용한 코드(등차수열 합 공식)

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

 

해석

 

예를 들어 n이 3개의 연속된 자연수(i-1, i, i+1)의 합으로 표현된다면 합은 3i가 됩니다. 즉, n은 3의 배수입니다. 마찬가지로 5개의 연속된 자연수의 합으로 n이 표현이 된다면 n은 5의 배수여야합니다. 따라서, n의 약수 중 홀수가 몇개있냐는 문제와 같은 문제로 해석할 수 있습니다.

 

초항 a이고 공차 1 인 n개의 등차 수열의 합이라고 보면 Sn = n(2*a + (n-1))/2가 되는데 i) n이 홀수 이면 (2*a + (n-1)) 는 짝수 이고 ii) n이 짝수 이면 (2*a - (n-1)) 는 홀수 입니다. 쉽게 생각하면 Sn = (홀수 * 짝수)/2 인데 나누기 2때문에 짝수는 홀수가 될수도 있고 짝수가 될 수 도 있습니다. 결국, 어떤 경우든 반드시 홀수의 숫자를 포함하고 있다는 것을 확인할 수 있습니다. 따라서, n을 나눌 수 있는 홀수의 갯수와 연속된 숫자의 경우의 수가 같다고 보는것 같습니다.

 

결론

n보다 작은 홀수로 나누어떨어지는 값의 갯수가 이 문제 답의 갯수