Search
Duplicate

수열의 합

주차
0
문제번호
1024
언어
티어
실버
유형
수학
이분탐색
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

수학적으로 푸는 방법이 떠오르지 않아서, 이분 탐색으로 풀었습니다.
L부터 시작하여 100까지 증가시켜갑니다
이분탐색은 첫 번째 숫자 기준으로 돌립니다.
한 번이라도 이분탐색을 성공시키면, 그 자리에서 출력시킵니다.

Code

제출 날짜

@3/17/2021

메모리

2016 KB

시간

0 ms
#include <iostream> #define MAX_ 1000000000 typedef long long ll; int N, L, ans; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> N >> L; ans = -1; } void binary_search(int b_min, int b_max, int length) { ll val = 0; if (b_min > b_max) return ; int b_mid = (b_min + b_max) / 2; for (int i = 0 ; i < length ; i++) val += (b_mid + i); if (val == N) { ans = b_mid; for (int i = 0 ; i < length ; i++) std::cout << b_mid + i << " "; return ; } if (val < N) binary_search(b_mid + 1, b_max, length); else binary_search(b_min, b_mid - 1, length); } void solve() { int i = L - 1; while (++i <= 100 && (ans == -1)) binary_search(0, MAX_, i); if (ans == -1) std::cout << ans; } int main() { input(); solve(); return (0); }
C++
복사