728x90
문제 링크: https://www.acmicpc.net/problem/2559
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
문제 풀이
누적 합을 이용하는 문제. 브루트 포스를 이용한다면 N이 최대 10만 이므로 시간 초과가 날 수 있다. 누적 합을 이용한 배열을 만들어주고, 예제 2를 생각하면 첫 번째는 prefix_sum[5]-prefix_sum[0]이고, 다음은 prefix_sum[6]-prefix_sum[1], ... 이렇게 앞에 있는 누적합을 빼주면서 구하면 O(N)이므로 시간 초과나지 않고 구할 수 있다.
코드
728x90
'BOJ' 카테고리의 다른 글
| [BOJ][Python] 백준 1001번 - A-B (0) | 2022.05.03 |
|---|---|
| [BOJ][Python] 백준 1000번 - A+B (0) | 2022.05.03 |
| [BOJ][Python] 백준 17265번 - 나의 인생에는 수학과 함께 (0) | 2022.05.01 |
| [BOJ][Python] 백준 8711번 - Odchudzanie (0) | 2022.05.01 |
| [BOJ][Python] 백준 25083번 - 새싹 (0) | 2022.05.01 |