백준 21758. 꿀 따기

https://www.acmicpc.net/problem/21758

21758번: 꿀 따기

 

그리디, 누적합 문제.

 

가장 간단한 방법은 벌,벌,통 세 개의 위치를 브루트포스로 구하는 것이 겠지만 시간이 안된다.

 

다음 세가지 경우로 나뉜다.

 

1. 벌 통 벌 

2. 벌 벌 통 

3. 통 벌 벌 

 

 

1번의 경우는 통이 두 벌 사이에 있는 경우인데, 이 때는 통은 무조건 가운데 위치해야 한다. 

 

2,3번 의 경우는 벌 한마리는 무조건 끝에 위치해야 하고, 나머지 한마리의 위치를 반복분으로 찾아서 계산해보면 된다. 

벌이 시작하는 위치는 꿀을 못따는데 벌 한마리가 무조건 끝에 위치해야 하는지에 대해 처음에 의문이 좀 들었다.

만약 맨끝에 엄청 큰 값이 있다면 안되는거 아닌가 생각할수 있는데 어처피 벌은 꿀통을 향해 일직선으로 움직이기 때문에 맨끝에 있는 꿀은 먹을 방법이 없다.