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

문제 확인

프로그래머스

나의 풀이

• i, j를 각각 연속된 수의 시작과 끝으로 생각하면, 각 i 마다의 j를 찾으면 문제를 풀 수 있다.
• 합을 구하는 과정에서 동일한 연산이 계속 반복되기 때문에, 누적합을 미리 계산했다.

def solution(n):
    answer = 0
    # 누적합
    cum_sum = []
    for i in range(10001):
        cum_sum.append((i * (i + 1) // 2))
    # 확인
    for i in range(10001):
        for j in range(i + 1, 10001):
            if cum_sum[j] - cum_sum[i] == n:
                answer += 1
            elif cum_sum[j] - cum_sum[i] > n:
                break
    return answer

다른 사람 풀이

• 시작점 a에서 k개 만큼의 연속된 숫자의 합은 $\frac{k(2a + k -1)}{2}$이며, 이 값이 $n$과 같아야 한다.
• 식을 정리하면 $a = \frac{n}{k} + \frac{1-k}{2}$으로 나타낼 수 있고, a와 k 모두 자연수라는 점을 고려하면, $k$는 $n$의 약수이고 $1 - k$는 짝수일 때 조건이 만족된다는 것을 알 수 있다.
• 이를 식으로 작성하면 아래와 같다.

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

---

참고

[Python] 프로그래머스 - 숫자의 표현 (연습문제/Level 2)