백준 [14931] 물수제비(Python3)
문제 링크 : https://www.acmicpc.net/problem/14931 14931번: 물수제비 (SUJEBI) 급격한 기후변화로 최근 대곽나라의 많은 강에서 생태계 교란종이 나타나고 있다. 이에 대곽나라의 이기범 대통령은 국무회의를 주재해 정부 차원의 대책을 논의하게 되었다. 대통령, 국무총리 www.acmicpc.net 완전 탐색 1 ~ 1,000,000 까지 순회하면서 간격을 1, 2, 3, ..., L을 두어 탐색했을 때 탐색한 값의 합이 가장 큰 걸 구한다. 간격별로 탐색 횟수를 나열해보면 아래와 같다. - 간격이 1일 땐, 1,000,000번 탐색. - 간격이 2일 땐, 500,000번 탐색. - 간격이 3일 땐, 333,333번 탐색. - 간격이 4일 떈, 250,000번 탐색. ...
백준 [2477] 수열의 합(Python3)
문제 링크 : https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 수학적 사고가 요구되는 문제. 뭔가 누적합을 사용할 수 있을 거 같아서 여기에 대해 1시간 정도 고민하다 도저히 안 돼서 풀이를 봤다. 완전 탐색 1부터 1,000,000,000까지 돌면서 각 지점에서 2부터 L까지의 합을 구한다. 총 시간 복잡도 O(N * (L - 2))로, N과 L이 최대 값일 때 시간 초과 완전 탐색 최적화 - 누적합 사용. 1부터 1,000,000,000까지의 누적합을 구한 뒤, 한 지점을 정하고 ..
