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

💻 문제 - Lv.2

---

👉 제출 코드

Sn = n * (n+1) / 2 를 생각하고 풀었다

def solution(n):
    answer = 1 # 자기자신
    for first in range(1, n//2+1):
        flag = False
        for last in range(first+1, n-first+1):
            if flag:
                break
            if (first+last) * (last-first+1) == 2 * n:
                answer += 1
                flag = True
    return answer

효율성 테스트 실패!

n = 15일 때

def solution(n):
    answer = 1 # 자기자신
    for first in range(1, n//2+1):
        flag = False
        for last in range(first+1, n-first+1):
            if flag:
                break
            print(first, last)
            if (first+last) * (last-first+1) == 2 * n:
                answer += 1
                flag = True
    return answer

first와 last의 값을 찍어보니 다음과 같다.

1 2
1 3
1 4
1 5
2 3
...
2 13
3 4
...
3 12
4 5
4 6
5 6
..
5 10
6 7
6 8
6 9
7 8

합이 n보다 클 때 예외 처리가 되지 않아 시간 초과가 뜬 것이다.

def solution(n):
    answer = 1 # 자기자신
    for first in range(1, n//2+1):
        flag = False
        for last in range(first+1, n-first+1):
            if flag:
                break
            print(first, last)
            if (first+last) * (last-first+1) == 2 * n:
                answer += 1
                flag = True
            elif (first+last) * (last-first+1) >= 2 * n:
                break
    return answer

elif를 추가하여 성공.

---

🙏 다른 사람의 풀이 보기

등차수열

결국 Sn = (홀수 * 짝수) / 2임을 이용한다면 다음과 같은 접근이 가능하다. (여기서 홀수는 결국 n의 약수)

# 풀이 1
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의 배수이다.
• n이 5개의 연속된 자연수의 합으로 표현된다면 n은 5의 배수이다.
• 따라서, n의 약수 중 홀수가 몇개 있냐는 문제와 같은 문제이다.

# 풀이 2
def expressions(num):
    answer = 0
    for i in range(1, num + 1):
        s = 0
        while s < num:
            s += i
            i += 1
        if s == num:
            answer += 1


    return answer

• 완점 탐색을 사용하여 예외처리한다