[swexpert] 7510. 상원이의 연속합 (c++, 누적합)
Posted by 해랑쓰 블로그 (Haerang's blog)
n이 최고 10^6이므로 n^2은 시간초과로 O(n)으로 풀어줘야 되는 문제이다. n=15일 때 1, 2, 3, ... ,15 를 하나씩 더하면 누적합은 1, 3, 6, 10, ... 이렇게 될 것이다. 6인 경우 1~6까지 누적합이 21이되어 15를 넘게 되면 앞에서부터 하나씩 빼준다 (연속합을 구하니깐) 21에서 1을 빼변 20, 2를 빼면 18, 3을 빼면 15가 되어 4+5+6=15 인 또 하나의 경우를 구할 수 있다. 그러니 시작이 어디부터 인지 나타내는 변수 s를 만들고 누적합이 15를 넘을 때마다 시작점을 1씩 증가시키면 된다. #define _CRT_SECURE_NO_WARNINGS #include using namespace std; int main(int argc, char** argv..