[프로그래머스] Lv0_연속된 수의 합

Lv0_연속된 수의 합

📄Description

연속된 세 개의 정수를 더해 12가 되는 경우는 3, 4, 5입니다. 두 정수 num과 total이 주어집니다. 연속된 수 num개를 더한 값이 total이 될 때, 정수 배열을 오름차순으로 담아 return하도록 solution함수를 완성해보세요.

제한 조건

• 1 ≤ num ≤ 100
• 0 ≤ total ≤ 1000
• num개의 연속된 수를 더하여 total이 될 수 없는 테스트 케이스는 없습니다.

입출력 예시

num	total	answer
3	12	[3,4,5]
5	15	[1,2,3,4,5]
4	14	[2,3,4,5]
5	5	[-1,0,1,2,3]

입출력 예 설명

1. num = 3, total = 12인 경우 [3, 4, 5]를 return합니다.
2. num = 5, total = 15인 경우 [1, 2, 3, 4, 5]를 return합니다.
3. 4개의 연속된 수를 더해 14가 되는 경우는 2, 3, 4, 5입니다.

---

🤔생각 정리

1. 음의 정수를 포함한 연속된 정수니까 반복문으로 계산하는 방법밖에 없으려나?
2. 최대값이 total을 넘을 수 없으니까 start를 total로 해서 while문을 사용해야겠네. end값을 모르니까.

💡Pseudo Code💡

1. start = total+1
2. while True:
3. 		lst = start-num 부터 start까지의 수
4.		lst의 합 == total:
5.			return lst
6.		start -= 1

---

🖥️코드화

def solution(num, total):
	start = total+1
    while True:
    	lst = list(range(start-num,start))
        if sum(lst) == total:
        	return lst
        start -= 1

시행착오) 시간 초과 케이스가 있다. 간단하게 해결하려고 했어서 `while`문 쓰려고 할 때 시간초과 문제가 있을 것 같았다.

다른 아이디어는 total / num으로 나눈 수, 즉 중앙값을 활용하는 것이다.
num이 짝수면 중앙값을 2개의 수로 num이 홀수면 중앙값을 1개로 두고 주변 숫자를 리스트에 추가하면서 생성하면 될 것 같다.

def solution(num, total):
    mid = total // num
    res = [mid] if num%2 else [mid, mid+1]
    while len(res) < num:
        res.insert(0, res[0]-1)
        res.append(res[-1]+1)
    return res

---

📌코드 비교 및 감상

1. 등차수열의 합 공식 활용

result = $[x+0, x+1, x+2, x+3 ... x + (num-1)]$로, 모두 더한 값이 total이 된다.
등차수열의 합 공식을 이용하면, total은 초항이 x, 마지막 항이 num-1이고 등차가 1인 등차수열의 합으로 표현할 수 있다.

코드를 인용하면 이렇다.

def solution(num, total):
    return [(total - (num * (num - 1) // 2)) // num + i for i in range(num)]

(연속된 수의 합공식을 이용해보려고 했다가 포기했는데 등차수열의 합 공식이 있었다. 다 배운건데 활용하는 게 어렵구나..)