알고리즘/백준 풀이
[백준 1024] 수열의 합
전태경
2018. 12. 17. 16:57
문제 출처 : https://www.acmicpc.net/problem/1024
문제 정리
- N과 L이 주어졌을 때, 합이 N이고, 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트 출력
- N 은 10^9보다 작거나 같은 자연수
- L 은 2보다 크거나 같고, 100보다 작거나 같은 수
문제 풀이
0 ~ 10^9 의 숫자로 시작하는 길이 L의 숫자 리스트의 합을 구하면 된다.
가장 짧은 길이이기에 L을 2부터 시작하면 된다.
하지만 10^9 * L 의 시간복잡도를 가지기 때문에 너무 많은 시간이 걸린다.
따라서, 0 ~ 10^9 를 이진탐색을 이용하여 구하면 시간초과를 해결할 수 있다.
(참고로 숫자 a 를 시작으로 하는 길이 l의 합의 공식은 = l * (2a + l-1) / 2 이다.)
또한 10^9 큰 숫자를 다루기때문에 long long 자료형으로 변환하는 것 또한 잊지말자.