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

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

 

이번 문제는 연속된 자연수로 n을 만들 수 있는 모든 경우의 수를 구하는 브루트포스 (brute force, 완전 탐색) 문제이다.

 

처음에는 dp 문제인 줄 알고 패턴과 점화식을 찾으려고 노력했으나, 도무지 규칙을 생각해봐도 나오지 않아 다른 사람의 풀이를 참고해본 결과 완전 탐색으로 풀이해야 한다는 것을 알게 되었다.(n <= 10000 이하의 자연수 이므로, 2중 반복문을 사용하여 O(N^2)의 시간복잡도를 가져도 무관)

 

2중 반복문을 사용하여 1, 1+2, 1+2+3, ... 와 같은 규칙으로 합을 계속해서 구하고, 만약 이 합이 n보다 크다면 더 이상 연산을 할 필요가 없으므로 break 해주었다.

 

가끔 이렇게 패턴이 보일 것처럼 생긴 문제에서 점화식을 찾으려다가 시간을 낭비하고 힘이 빠져버리는 경우가 있는데, 다음부터는 완전 탐색을 먼저 고려해보고 시간복잡도가 여유롭다면 완전 탐색으로 푸는 연습을 해야겠다 :)