문제:
N과 L이 주어질 때, 합이 N이면서, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하는 프로그램을 작성하시오.
입력:
첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.
출력:
만약 리스트의 길이가 100보다 작거나 같으면, 연속된 수를 첫째 줄에 공백으로 구분하여 출력한다. 만약 길이가 100보다 크거나 그러한 수열이 없을 때는 -1을 출력한다.
풀이방법:
처음에는 이 문제를 투포인터를 사용하는 방법으로 접근하였다. list의 합이 N과 같으면 길이를 비교하여 저장하도록 하였고, N보다 작으면 리스트의 길이를 늘려주고 N보다 크면 리스트의 길이를 줄여주도록 하였다.
하지만 이 방법은 N의 크기에 따라 시간이 많이 증가할 수 있다는 단점을 가지고 있었고 결국 시간초과가 발생하게 되었다. 코드는 다음과 같다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
import copy
N, L = map(int,input().split())
list_ = list(range(1,L+1))
start, end = 1,L
answer = [0]*100
while list_[0] <= N//2:
if sum(list_) == N:
if len(list_) < len(answer):
answer = copy.deepcopy(list_)
list_.pop(0)
elif sum(list_) < N:
list_.append(end)
end+= 1
else:
list_.pop(0)
start+= 1
if len(answer) > 100 or len(answer) < L:
print(-1)
else:
print(*answer)
|
cs |
따라서 다른 방법을 생각해보았는데, 이 문제를 수학적으로 접근해보았다.
우선 길이가 L인 연속된 수들의 합이 N이 되는 수열은 항상 존재한다고 가정한다. 그리고 그 수열의 첫 시작 수를 X라고 할 때, 다음과 같이 식을 표현할 수 있다.
N = X + (X+1) + (X+2) + (X+3) + ... + (X+L-1)
이를 정리하면 다음과 같이 표현할 수 있다.
N = LX + (1+2+3+...+L-1)
= LX + (L-1)L/2
그럼 X는 다음과 같이 구할 수 있다.
X = N/L - (L-1)/2
따라서 L을 증가 시키면서, 음이 아닌 정수가 되는 X를 찾으면 된다. 그리고 만약 L이 100이 넘어간다면 -1을 문제 조건에 따라 출력하도록 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
N, L = map(int,input().split())
answer = -1
while True:
if L > 100:
break
temp = N/L-(L-1)/2
if temp < 0:
L+=1
continue
if int(temp) == temp:
answer = int(temp)
break
L+=1
if answer >= 0:
print(*range(answer,answer+L))
else:
print(-1)
|
cs |
문제링크:
https://www.acmicpc.net/problem/1024
1024번: 수열의 합
첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다.
www.acmicpc.net
'Algorithm > Python' 카테고리의 다른 글
| [BOJ]2240. 자두나무 (0) | 2021.06.08 |
|---|---|
| [BOJ]2302. 극장 좌석 (0) | 2021.06.03 |
| [BOJ]1826. 연료 채우기 (0) | 2021.05.27 |
| [BOJ]1422. 숫자의 신 (0) | 2021.05.25 |
| [BOJ]15686. 치킨 배달 (0) | 2021.05.20 |