TIL : 벌꿀 채취 (SWEA)

문제 정보

• 문제 이름: [모의 SW 역량테스트] 벌꿀채취 (SWEA 2115번)
• 문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
• 알고리즘 분류: 완전 탐색 (Brute Force), 백트래킹 / DFS, 조합 (Combination)

---

풀이 과정

1. 문제 분석 및 제약 조건 확인

• 문제 요약:
• $N \times N$ 크기의 벌통 격자에서 두 명의 일꾼이 각각 가로로 연속된 $M$개의 벌통을 선택합니다.
• 두 일꾼이 선택한 벌통 영역은 서로 겹쳐서는 안 됩니다.
• 각 일꾼은 자신이 선택한 $M$개 벌통 중 일부 또는 전체를 골라 꿀을 채취할 수 있으며, 채취한 꿀 양의 총합은 최대 $C$를 넘을 수 없습니다.
• 수익은 채취한 각 벌통 꿀 양의 제곱의 합으로 계산됩니다. 두 일꾼이 얻을 수 있는 수익 합의 최댓값을 구해야 합니다.

• 제약 조건:
• 격자 크기 $N$: $3 \le N \le 10$
• 선택할 벌통 개수 $M$: $1 \le M \le 5$ (단, $M \le N$)
• 꿀 채취 한도 $C$: $10 \le C \le 30$
• 각 칸의 벌꿀 양: $1 \le \text{꿀의 양} \le 9$

---

2. 알고리즘 및 자료구조 선택

• 문제 분할 접근:
• [소문제] 길이 $M$의 연속된 구간에서 합이 $C$ 이하인 부분집합 중 제곱의 합이 최대가 되는 값 계산
• [대문제] 격자판 전체에서 두 일꾼이 겹치지 않게 가로 $M$개 구간 2개를 골라 수익의 합을 최대로 만드는 조합 탐색

• 선택한 알고리즘:

1. DFS (백트래킹): $M \le 5$이므로 각 벌통을 "선택한다/안 한다"로 분기하는 경우의 수는 최대 $2^5 = 32$가지입니다. 재귀 완전 탐색을 사용하며, 합이 $C$를 초과할 경우 즉시 가지치기(Pruning)합니다.
2. 2차원 배열 전처리 (Memoization / Precomputation): 가능한 모든 시작점 $(r, c)$에 대해 얻을 수 있는 최대 수익을 2차원 리스트 profit[r][c]에 미리 계산해 둡니다.
3. 조합 탐색 (4중 반복문): 일꾼 1의 시작점 $(r_1, c_1)$을 고정하고, 겹침 조건을 고려하여 일꾼 2의 시작점 $(r_2, c_2)$를 탐색합니다.

---

3. 절차적 구현 흐름

1. 최대 수익 계산 함수 구현 (get_max with DFS):

• 인덱스 idx, 현재까지 채취한 꿀의 합 cur_sum, 현재까지의 제곱 수익 합 cur_profit을 상태값으로 전달합니다.
• cur_sum > C이면 즉시 return합니다.
• idx == M에 도달하면 모든 벌통에 대한 선택이 끝난 것이므로 max_profit을 갱신하고 반드시 return으로 탐색을 종료합니다.
• 현재 벌통을 채취하는 분기와 채취하지 않고 건너뛰는 분기 2가지로 재귀 호출합니다.

2. 모든 구간 최대 수익 전처리 (profit 배열 채우기):

• $N \times (N - M + 1)$ 크기의 profit 2차원 리스트를 생성합니다.
• 각 좌표 $(y, x)$에서 grid[y][x : x + M] 구간을 잘라 get_max 함수를 호출하고 그 결과를 profit[y][x]에 저장합니다.

3. 두 일꾼의 위치 조합 탐색 및 최댓값 갱신:

• 일꾼 1의 시작점 $(y_1, x_1)$을 순회합니다.
• 중복 탐색 방지를 위해 일꾼 2의 행 $y_2$는 $y_1$부터 $N-1$까지만 탐색합니다.
• 겹침 방지 처리:
• $y_1 == y_2$ (같은 행)인 경우: 일꾼 2는 일꾼 1의 영역이 끝난 이후인 $x_1 + M$ 열부터 시작합니다.
• $y_1 < y_2$ (다른 행)인 경우: 행이 다르므로 일꾼 2는 $0$번 열부터 시작할 수 있습니다.

• profit[y1][x1] + profit[y2][x2] 값 중 최댓값을 찾아 출력합니다.

---

4. 시간 복잡도

• 1구간 내 최대 수익 계산 (DFS):
• 각 원소마다 2가지 선택지가 있으므로 한 구간당 $O(2^M)$ 연산이 소요됩니다. ($M=5$일 때 최대 32번)

• 전처리 시간 복잡도:
• 총 구간의 개수는 $N \times (N - M + 1)$개입니다.
• 전체 전처리 시간: $O(N \cdot (N - M + 1) \cdot 2^M)$ $\rightarrow$ 최악의 경우 $10 \times 6 \times 32 = 1,920$번 연산

• 두 일꾼 조합 탐색 시간 복잡도:
• 총 구간 개수를 $K = N(N - M + 1) \le 60$이라 할 때, 두 구간을 고르는 조합 수는 최대 $\frac{K(K - 1)}{2} \approx 1,770$번 순회합니다.

• 총 시간 복잡도:
• $O(N^2 \cdot 2^M + N^4)$
• 전체 연산 횟수가 약 4,000번 내외로, 제한 시간(파이썬 기준 수 초) 대비 0.01초 이내에 여유롭게 통과합니다.