[파이썬/알고리즘] 프로그래머스 - 숫자의 표현 (Brute force, 완전 탐색)

[문제]

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 이하의 자연수 입니다.

 

[풀이]

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

 

Brute force, 완전 탐색 문제이다.

 

count = 0

n이 되는 경우의 수를 센다.

 

for i in range(1, n+1):

n 이하의 숫자들에 대해서 반복문을 돌린다.

 

sum = 0

숫자를 검정하기 위한 합계를 만들어준다.

 

for j in range(i, n+1):

각 숫자들을 합하면서 로직을 검사한다.

 

sum += j

sum_val에 합쳐준다.

 

if sum == n:

   count += 1

만약 합계가 n과 같을 경우에 횟수를 +1 해준다.

 

elif sum > n:

      break

n보다 클 경우엔 break문으로 빠져나간다.

크게 되면, 더 이상의 연산이 불필요해지므로 빠져나간다.

 

return count

횟수를 반환한다.

 

 

로직을 설명하자면, 첫 번째 반복문에서 1,2,3 ... n까지 반복된다.

처음 실행되면 첫 반복문에서 1이 들어오고 두 번째 반복문이 실행된다.

 

두 번째 반복문에서 1부터 n까지의 숫자를 반복해서 더하다가 n이랑 같아지면 횟수를 반환한다.

만약 더하다가 n보다 커지는 경우에는 두 번째 반복문을 빠져나가고 첫 번째 반복문으로 간다.

 

만약 10이 들어왔다고 한다면 1의 경우에는 1 + 2 + 3 + 4에서 10이 나오므로 횟수를 추가해준다.

2의 경우에는 2 + 3 + 4 + 5 + 6은 20이 되버리므로 10보다 커서 elif sum_val > n에 의해서 빠져나간다.

 

그렇게 3에 대해서, 4에 대해서, 5에 대해서, 마지막으로는 10에 대해서까지 반복하고 종료된다.

 

즉 모든 경우의 수를 전부 탐색하는 방식이다.