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

입출력 예

입출력 예

입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

---

나의 풀이

def solution(n):
    answer = 0
    for i in range(1, 140): # 1 ~ 140까지 합이 9870으로 10000 미만의 수 중 가장 큰 수
        if n < i + sum(range(i)): break # n이 1 부터 i 개를 더한 값보다 작은 경우
        if (n-sum(range(i)))/i == int((n-sum(range(i)))/i): # 나누어 떨어짐 -> 패턴에 일치하는 경우
            answer += 1
    return answer

일정한 규칙을 찾으면 된다.

x부터 1개의 합 -> x + 0
x부터 2개의 합 -> 2x + 1
x부터 3개의 합 -> 3x + 3
x부터 4개의 합 -> 4x + 6
x부터 5개의 합 -> 5x + 10
x부터 6개의 합 -> 6x + 15
x부터 7개의 합 -> 7x + 21
x부터 8개의 합 -> 8x + 28
...
x부터 n개의 합 -> nx + (n-1까지 합)

예를 들어 x부터 3개의 합을 보면 x부터 차례대로 x, x+1, x+2이다. 이 세 숫자를 합하면 3x + 3이 된다.

이 규칙을 코드로 다음과 같이 나타낼 수 있다.

n*x+sum(range(n))

 

for문으로 1부터 140까지 반복한다. i는 몇 개의 숫자로 표현할 수 있는지를 나타내고, 140인 이유는 1~140까지 합을 구하면 9870으로 이 문제의 제약조건인 10000을 넘기지 않는 가장 큰 수이기 때문이다.

n*x+sum(range(n)) 에서 x에 1을 넣으면 1부터 n까지의 합이 된다. 확인하고자 하는 숫자가 이 수보다 작아지면 더 이상 확인할 필요가 없다.

해당 개수로 표현할 수 있는지 확인하는 방법은 역시 i*x+sum(range(i)) 이 식을 사용하면 된다.

확인하고자 하는 수(n)에서 sum(range(i))을 뺀 후 i로 나눴을 때 나누어 떨어지면 표현이 가능한 것이다.

표현이 가능하다면 answer에 1을 추가해준다.

테스트 결과n*x+sum(range(n))