반응형
문제
https://www.acmicpc.net/problem/2559
2559번: 수열
첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기
www.acmicpc.net
풀이
누적 합을 사용해서 풀이할 수 있습니다.
구간이 고정되어 있기 때문에, 슬라이딩 윈도우를 사용해서도 풀이할 수 있습니다.
구간의 크기가 k이고 누적 합을 사용하면,
누적합 배열의 array[i + k] - array[i]로 구간의 온도의 합을 구할 수 있습니다.
슬라이딩 윈도우를 사용하면,
초기의 합은 array[0] ~ array[k - 1] 합이 될 것이고,
이 합에서 array[0]을 빼고, array[k]를 더해주면 자연스럽게 array[1] ~ array[k] 구간의 합을 구할 수 있습니다.
이를 0부터 n - k 번 까지 반복한다면 모든 구간의 합을 구할 수 있습니다.
소스코드
후기
구간의 사이즈가 정해져 있기 때문에, 누적 합과 슬라이딩 윈도우를 사용하여 풀이할 수 있는 문제였습니다.
사이즈가 고정적이지 않다면.. 투포인터 알고리즘을 사용했어야 할지도..?!
반응형
'PS > 백준' 카테고리의 다른 글
| [BOJ] 백준 10986 나머지 합 (Swift) (0) | 2023.04.07 |
|---|---|
| [BOJ] 백준 16139 인간-컴퓨터 상호작용 (Swift) (0) | 2023.04.07 |
| [BOJ] 백준 11659 구간 합 구하기 4 (Swift) (0) | 2023.04.07 |
| [BOJ] 백준 12865 평범한 배낭 (Swift) (0) | 2023.04.07 |
| [BOJ] 백준 9251 LCS (Swift) (0) | 2023.04.07 |
