[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/12924
📌문제 설명
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 = 15
result = 4
💡 문제 풀이
항상 계산이 간단한(?) 문제들을 완전탐색으로 를 풀면 시간초과가 날 것 같은 불안함이 든다...😂
하지만 별다른 공식이나 아이디어가 떠오르지 않았고 알고리즘 문제 해결시 처음 접근해야하는 방법도 완전탐색은 맞으니(모든 경우에 대한 생각이 필요하다는 뜻!) 이중 반복문과 조건문을 이용한 단순한 방법으로 문제를 해결하였다.
먼저, n 자연수 하나도 방법의 수에 해당되기 때문에 answer는 1로 책정!
연속되는 자연수의 시작지점과 끝지점을 정하기 위해서 이중 반복문을 사용하였다.
ex) 15 = 4 + 5+ 6의 경우 시작지점은 '4' 끝지점은 '6'
파이썬은 sum함수를 이용하여 리스트(list)의 합을 쉽게 구할 수 있기 때문에 1부터 n-1까지의 자연수를 리스트에 담았고 이중 반복문의 값을 인덱스로 이용하여 합이 n가 일치하는지 확인하였다.
ex) numbers = [1, 2, 3, 4, 5, 6, 7 ...] → sum(numbers[3:6]) = 15
단, 모든 경우의 수를 따지게 되면 불필요한 계산이 생기므로 효율성을 위해 합이 n보다 클 경우 break하였다.
def solution(n):
answer = 1
numbers = [i for i in range(1, n)]
print(numbers)
for i in range(0, len(numbers)-1):
for j in range(i+1, len(numbers)):
res = sum(numbers[i:j+1])
if res == n:
answer += 1
if res > n:
break
return answer아니나 다를까 '다른사람의 풀이'에서 수학공식(등차수열의 합)을 이용한 풀이가 있었다...
def expressions(num):
return len([i for i in range(1,num+1,2) if num % i is 0])