BOJ 21758 (꿀 따기) - CT 풀이

 문제가 꿀 얘기이다 보니까 예전에 군대에서 이등병 때에 여러 이유로 잡일에 빠졌다고 꿀벌이라고 불렸던 기억이 났습니다. (물론 그 이후로는 아주 성실하게 만기로 전역했습니다.) 그런데 잘 생각해보니 꿀벌 입장에서는 열심히 일을 하는 것 뿐인데, 꿀을 빤다는 얘기가 인간들에게는 게으르고, 할 일을 잘 뺀다는 의미로 쓰는 걸 안다면 참 억울하게 느껴질지도 모르겠네요 ㅎㅎ

 

---

 

21758번: 꿀 따기

 

문제 설명)

 이 문제는 수열이 주어지고, 해당 수열에서 두 벌의 위치와 꿀통의 위치를 조절해서 모을 수 있는 최대의 꿀의 양을 구하는 문제입니다. 여기서 벌은 각각 꿀통까지 일직선으로 날아가면서 순차적으로 지나가는 숫자들만큼의 꿀을 모읍니다. 다만, 두 벌의 출발점에 해당하는 꿀은 두 벌 모두 가질 수 없고, 한 마리가 이미 지나갔다고 해서 그 다음으로 오는 벌이 지나가는 타일에 해당하는 꿀을 못 모으거나 하지는 않습니다. (벌통 역시 두 마리의 벌 모두 벌통 타일에 해당하는 꿀의 양을 얻을 수 있습니다.)

 

---

문제 풀이)

 저는 일단 두 마리의 벌과 벌통의 위치를 세 가지로 나누어 생각했습니다. 

 

1. 벌, 벌, 꿀통

2. 꿀통, 벌, 벌

3. 벌, 꿀통, 벌

 

 그리고, 각각의 최대 이익이 될 수 있는 경우를 구한 다음에 그 셋을 비교하여 답을 도출했습니다. 물론 그렇다고 모든 경우의 수를 고려해야 하는 것은 아니고, 각각 최대로 꿀을 모으기 위해서는 어느정도 위치가 정해진 경우도 존재했습니다.

 

1) 🐝, 🐝, 🍯

 이 경우는 무조건 꿀통은 맨 오른쪽 끝에 있고, 벌 한 마리는 맨 왼쪽 끝에 있어야 최대로 꿀을 모을 수 있습니다. 즉, 이 위치만 고정해 놓고 다른 벌의 위치를 바꿔가면서 누적합을 구해야 합니다.

🐝

🍯

2) 🍯, 🐝, 🐝

 이 경우도 위와 마찬가지입니다. 다만, 이번에는 꿀통이 맨 왼쪽 끝으로, 벌 한 마리가 맨 오른쪽 끝으로 가야할 것입니다.

🍯

🐝

 

3) 🐝, 🍯, 🐝

 꿀통이 가운데 있는 경우에는 두 벌의 위치가 양쪽 끝에 위치해야 가장 많은 꿀을 모을 수 있습니다. 그렇기 때문에 두 벌을 맨 끝으로 고정하고 꿀통의 위치만 바꿔가면서 누적합을 구하면 됩니다. 

🐝

🐝

 

 예를 들어 9 9 4 1 4 9 9 라면, 사실 1번과 2번 경우를 하나로 생각해도 됩니다. 왜냐면 숫자가 좌우로 완전히 대칭이기 때문입니다. 그렇기에 이렇게 입력값이 나오면 푸는 입장에서는 아주 감사한 일이 아닐 수 없겠죠? 여튼, 그럼 이제 1번과 3번의 경우만 나눠서 누적합을 구해보면 풀 수 있겠습니다.

 

1) 🐝, 🐝, 🍯

 

	🐝	🐝	4	1	4	9	9 🍯
꿀 양	27	27					총 54

	🐝	9	🐝	1	4	9	9 🍯
꿀 양	32		23				총 55

	🐝	9	4	🐝	4	9	9 🍯
꿀 양	35			22			총 57

	🐝	9	4	1	🐝	9	9 🍯
꿀 양	32				18		총 50

	🐝	9	4	1	4	🐝	9 🍯
꿀 양	27					9	총 36

 

 

3) 🐝, 🍯, 🐝

 

	🐝	9 🍯	4	1	4	9	🐝
꿀 양	9	총 36					27

	🐝	9	4 🍯	1	4	9	🐝
꿀 양	13		총 30				18

	🐝	9	4	1 🍯	4	9	🐝
꿀 양	14			총 28			14

	🐝	9	4	1	4 🍯	9	🐝
꿀 양	18				총 31		13

	🐝	9	4	1	4	9 🍯	🐝
꿀 양	27					총 36	9

 

 즉, 이 경우에는 57이 답이 됩니다.