oVeron

https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 관찰, 알고리즘 꿀통 위치, 두 벌의 위치를 일일이 정하고 꿀의 합까지 구한다면 시간 초과가 날 것이다. 누적 합을 사용한다면 꿀의 합을 빠르게 구할 수 있을 것이다. 그렇다면 꿀통 위치, 두 벌의 위치를 어떻게 구해야 하는가? 꿀통 위치가 두 벌 사이에 있지 않다고 가정해 보자. 이때, 꿀통과 어떤 한 벌은 반드시 맨 끝 장소에 있어야 한다. 그렇지 않다면 무조건 꿀 양에서 손실을 볼 수밖에 없다. 나머지 한 벌은 그 사이의 장소에 위치시키며 누적 합을 이용해 최댓값을 구하면 된다. 이번에는 꿀통 위치가 두 벌 사이에 있다고 가정해 보..

알고리즘/baekjoon 2023. 4. 30. 12:30