[프로그래머스]숫자의 표현(Python)

0. 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

 

1. 문제 설명

1) 1부터 n까지 연속된 자연수의 합이 n인 방법의 수 찾기

 

2. 입출력

# input
n = 15

# output
result = 4
"""
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
"""

 

3. 코드

첫 번째 코드

def solution(n):
    answer = 0

    for i in range(1, n + 1):           # 1부터 n+1까지 반복
        sum = 0                         # 연속된 자연수를 더한 합
        for j in range(i, n + 1):       # i부터 n+1까지 반복
            sum += j                    # 합에 자연수 더하기
            if sum > n:                 # 합이 n보다 크면
                pass                    # 나머지 반복문은 패스
            if sum == n:                # 합이 n 이면
                answer += 1             # 1가지 방법 찾음
                pass                    # 나머지 반복문은 패스

    return answer

 

실행 결과

문제의 조건만 읽고 순수하게 코드를 작성했는데 효율성 테스트를 통과하지 못했다

 

두 번째 코드

def solution(n):
    answer = []
    
    for i in range(1, n, 2):        # 홀수이면서
        if n % i == 0:              # n의 약수인 경우
            answer.append(i)

    return len(answer) + n % 2      # n이 홀수면 한 번 더 가능

 

실행 결과

a + (a+1) + ... + (a+k-1) = (2a+k-1) * (k/2) 식에서 a = (n/k) + (1-k)/2 를 이용하였다.

a가 자연수가 되려면 k는 n의 약수, 1-k는 2의 배수(짝수), 즉 k는 홀수가 되어야 한다.

따라서 k는 n의 약수이면서 홀수인 경우가 되어야 하므로 for 문으로 코드를 작성해준다.

문제에서 제시한 케이스인 15 의 경우 k=2일 때 한 번 더 가능하므로 n이 홀수일 때 하나를 추가한다.

 

5. Github

https://github.com/iihye/Algorithm/blob/main/Programmers/express_number.py

GitHub - iihye/Algorithm