[프로그래머스] 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 이하의 자연수입니다.

 

입출력 예

n	return
15	4
1	1

 

해답 및 해설

파이썬 (Python)

방식 1

def solution(n):
    sqrt_n = int((2*n)**(1/2))  

    answer = 1
    if n%2 == 1 and n>1:
        answer += 1
    
    for k in range(3, sqrt_n+1):
        if 2*n%k == 0:
            a = (2*n//k - k + 1)/2
            if int(a) == a and a>0:
                answer += 1
    return answer

k(2a+k-1) / 2

 

연속된 숫자 중 시작하는 숫자가 a, 숫자의 개수를 k라고 했을 때 그 숫자들의 합은 위와 같이 표현된다. 우선 k는 2n의 약수이다. 또 k <2a+k-1이므로, k는 2n의 제곱근보다 작다. 따라서 해당 범위 내에서 k가 나누어지는지 확인하고, 나누어지면 나머지 공식 규칙에 맞는지 확인해주면 된다.

 

또 해법 중 무조건 연속되는 숫자가 한 개인 경우는 항상 포함되고, 홀수일 경우 연속되는 숫자가 두 개인 경우가 항상 있으므로 그 경우의 수는 빼주었다. 또 n=1인 경우는 예외 처리를 해주었다.

 

방식 2

def solution(n):
    answer = 0
    
    # 홀수인 수로만 나누어보기
    for i in range(1, n + 1, 2):
        if n % i == 0:
            answer += 1

    return answer

k(2a+k-1) / 2

 

위 식에서 k와 2a+k-1은 서로의 홀짝이 달라야 하는 관계이다. 둘 중 하나는 2의 인수가 있으므로 항상 짝수여야 하고, 그러면 나머지 수는 위 식에 맞아떨어지려면 항상 홀수가 된다. 따라서 홀수인 약수가 몇 개인지 개수만 세어주면 된다.