-
BOJ 21921 블로그알고리즘/백준 2022. 2. 11. 16:06
슬라이딩 윈도우 기법으로 풀면 간단하다. 맨 처음은 그렇게 생각해서 문제를 풀었는데 슬라이딩 윈도우 알고리즘이 잘 생각이 되지 않아서 다이나믹 프로그래밍(?) 기법으로 풀어냈다.
먼저 dp 배열의 각 index는 1~index까지의 합계이다.
여기서 구간 합을 구하게 되는데 구간의 크기가 고정되어 있다보니
점화식을 다음과 같이 만들 수 있었다.
int num = dp[i] - dp[i-k];
여기서 i < k인 경우는 포함하지 않으며, 해당 점화식을 통해서 구하면
2,3의 구간합을 구하는 경우
dp[1]은 1~1번째의 합, dp[3]은 1~3번째의 합이므로 2~3번째의 합이 도출된다.
이렇게 구한 num의 값을 통해서 최대값을 구할 수 있었다.
두 번째 값의 경우는 num 값을 ArrayList에 저장한 후 내림차순으로 정렬한다.
그 뒤 list를 돌면서 num > list의 값이면 탐색을 중단하는 식으로 만들었다.
허나 이것보다 더 좋은 방법은 많을 것이라고 생각하고, 아마 1번째 답을 탐색하는 과정에서도
Integer의 compare 함수를 통해서 더 효율적으로 만들 수 있을 것이라 생각한다.
'알고리즘 > 백준' 카테고리의 다른 글
BOJ 1238 파티 (0) 2022.01.28 BOJ 9177 단어 섞기 (0) 2022.01.26 BOJ 1613 역사 (0) 2022.01.21 BOJ 11404 플로이드 (0) 2022.01.20 BOJ 11051 이항 계수 2 (0) 2021.12.27