[프로그래머스] 숫자의 표현 (level2, python)

문제 설명

 

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	reseult
15	4

---

입출력 예 설명

 

입출력 예#1

문제의 예시와 같습니다.

 

 

풀이 코드

def solution(n):
    answer = 0
    
    for i in range(1, n+1):
        sum_val = 0
        for j in range(i, n+1):
            sum_val += j
            if sum_val == n:
                answer += 1
            elif sum_val > n:
                break
                
    return answer

 

브루트포스 (brute force, 완전 탐색) 문제이다. 

처음에는 dp 문제인 줄 알고 점화식 규칙을 이끌어 내려고 했으나, 도무지 규칙을 생각해봐도 나오지 않아 완전 탐색으로 접근했다.

n <= 10000 이하의 자연수 이므로, O(N^2)의 시간복잡도 로직을 구성해도 될 것이라 판단했다.

 

먼저 1부터 연속된 숫자의 합을 구한다.

1, 1+2, 1+2+3, ... 와 같은 규칙으로 합을 계속해서 구하고, 만약 이 합이 '같게 만들고자 하는 값'보다 크다면 더 이상 더해줄 필요가 없으므로 break를 걸었다.

 

그 다음은 2부터 연속된 숫자, 3부터 연속된 숫자의 패턴으로 완전탐색을 진행했다.

기본적으로 2중 for문으로 구성되어있으므로, for문 내의 로직에 O(N) 이상인 코드가 들어가면 효율성에서 탈락할 것이므로 이 점을 유의해서 로직을 구성하자.