문제 출처 : 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 자료형으로 변환하는 것 또한 잊지말자.
'알고리즘 > 백준 풀이' 카테고리의 다른 글
| [백준 2167] 2차원 배열의 합 (0) | 2018.12.19 |
|---|---|
| [백준 3055] 탈출 (0) | 2018.12.18 |
| [백준 7562] 나이트의 이동 (0) | 2018.12.17 |
| [백준 1328] 고층 빌딩 (1) | 2018.11.29 |
| [백준 9465] 스티커 (0) | 2018.11.25 |
