[백준 시리즈] 1024번 : 수열의 합 - 실버 2 / Python

1024번 : 수열의 합 - 실버 2 / Python

출처 : 백준 /  1024번: 수열의 합 (acmicpc.net)

사용 알고리즘 : 수학

 

문제 설명

N과 L이 주어질 때, 합이 N이면서 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하시오.

 

제한

시간 제한 : 2초 / 메모리 제한 : 128MB

N은 1,000,000,000 이하의 자연수이다.

L은 2이상 100이하인 자연수이다. 

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

시간복잡도를 가늠하기 어렵다.

N을 기준으로 시간복잡도를 구성한다면, O(logN) 이하의 알고리즘이 필요하다.

 

2단계 : Naive하게 풀어보자

배열의 요소는 1~N까지 순차적이므로 등차 수열의 합 공식을 이용하여 순서쌍을 선택하는 문제로 변경할 수 있다. 배열이 정렬되어 있고 순서쌍을 선택하는 문제이므로 투 포인터를 이용하면 쉽게 해결될 것 같다. 하지만, 가장 짧은 리스트를 찾아야 하므로 투 포인터를 사용하게 되면 최악의 경우 대략 5억번의 연산을 수행해야 한다.

 

a1 < a2인, (a1, a2)에 대해 a2에 따라 a1을 이분 탐색 하더라도 5억번의 연산을 수행해야 한다.

 

3단계 : 핵심 아이디어는 무엇인가

길이는 최대 100 밖에 안되므로, 길이에 따라 N을 찾는다.

길이(l)	항	합
2	a, a+1	2a+1
3	a, a+1, a+2	3a+(1+2)
4	a, a+1, a+2, a+3	4a+(1+2+3)
일반화	a, a+1, a+2, ...	la + l(l - 1) / 2

이다.

 

N = la + l(l - 1) / 2 이므로, L부터 100까지 a에 대해 계산하고 음이 아닌 정수인지 판별하여 가장 먼저 조건을 만족할 때 정답을 출력한다.

 

1) a가 음이 아닌 정수인지 판별하는 방법

• N - l(l-1)/2가 l로 나누어떨어지는지 확인한다.
• a를 int형으로 변환하여 재계산하여 N이 나오는지 확인한다.

 

정답 코드

n, l = map(int, input().split())
for i in range(l, 101):
    la = n-((i*(i-1))//2)
    if la>=0 and la%i == 0:
        print(*[j for j in range(la//i, (la//i)+i)])
        exit()
print(-1)

 

 

---