요약 설명:
자연수 n이 주어질 때, n이하의 연속된 자연수의 합이 n이 되는 경우가 몇개인지 세서 반환한다.
이게 첫번째로 짠 코드다.
나중에 보니 나도 무슨말인지 모르겠다.
def solution(n):
answer = 0
counter = 0
s = 1
while True:
sum = 0
counter = 0
for i in range(s, n + 1):
sum += i
if sum < n:
True
elif sum == n:
break
elif sum > n:
counter = 1
break
if s < n :
s += 1
elif s == n:
answer += 1
break
else :
break
if counter == 0 :
answer += 1
return answer대충 보니 아래의 것에서 외부 for문을 while문으로 만든거 같고 나머지는 비슷하다.
while문으로 하려다보니 counter도 들어갔고 줄도 되게 길어졌다.
아래는 두번째로 짠 코드.
훨씬 간결해졌다.
def solution(n):
answer = 0
for i in range(1, n+1):
temp = 0
for j in range(i,n+1):
temp += j
if temp > n: #8번째 줄
break #9번째 줄
if temp == n:
answer+=1
break
return answer두번째로 짠 코드는 매우 직관적이다.
하지만 이중for문 때문에 효율성테스트에서 시간초과가 된것.
8번째, 9번째 줄을 추가해 해결했다.
두 줄의 역할은 단순하게도 합(temp)이 n보다 커지면 그냥 그즉시 멈추고 다음 숫자부터 덧셈을 시작한다.
테스트 케이스로 n = 15 일때
2부터 더하기 시작할 때
저 두줄이 없으면 15가 넘어가도 계속 더하고 결국 14번 다돌게된다.
만약 숫자가 커지면 말도 안되게 커질것.
2중 for문이라 시간복잡도가 O(n^2)여서 n의 제약조건이 없거나 더 큰수였다면 아마 더 최적화가 필요했을 것으로 보인다.
찾아보니 dp를 활용해 푸는 문제라고 한다.
