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

1. 완전탐색을 활용한 풀이

완전 탐색을 이용한 문제는 가장 쉽게 떠올릴만한 풀이과정이다.

1부터 n까지의 수를 차례대로 탐색하며,

연속된 합인 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8 = 15 임을 찾아내고,

2 + 3 + 4 + 5 + 6 의 경우 2 + 3 + 4 + 5 = 14에서 2 + 3 + 4 + 5 + 6 = 20으로 가기 때문에

해당되지 않음을 알 수 있다.

이를 코드로 나타내면 아래와 같다.

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

2. 등차수열의 합을 이용한 풀이

알고리즘 문제를 풀 때, 적당한 변수를 x로 두고 수학적으로 접근하는 것이 중요한 열쇠가 될 수 있다.

이 문제의 경우 연속된 숫자들 중 제일 작은 값을 x라 하면,

x + (x + 1) + (x + 2) + ... + (x + i - 1) 으로 나타낼 수 있다.

이 합을 n이라하면, n = i*(2x + i - 1) / 2가 되고 이를 x에 대해 정리하면

x = n / i + (1-i) / 2 가 되고, 문제에서의 조건은 x가 자연수여야한다.

 

x가 자연수려면, i는 이미 자연수이기 때문에, 1 - i / 2는 정수여야하고, 그러기 위해선 i는 홀수여야 한다.

또한 n / i 역시 자연수여야하는데, 그러기 위해선 i가 n의 약수여야한다.

따라서 조건을 정리하면,

1) i는 홀수 (range(1, n+1, 2))

2) i가 n의 약수 (if n % i is 0)

위와 같고 이를 코드로 나타내면 아래와 같다.

def solution(n):
    return len([i  for i in range(1,n+1,2) if n % i is 0])

 

완전탐색을 이용해 비교적 간단하게 풀 수도 있지만, 구하려는 것을 x로 놓고 문제를 차근차근 해결하는 수학적 접근 방식의 중요성을 다시 한번 느낄 수 있었다.