https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&&
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
풀이 과정
문제의 조건에 맞게 주어진 벌통을 선택할 때, 선택한 벌통내에서 채취할 수 있는 가치의 최대값을 구하는 문제이다.
일꾼이 벌통을 선택하는 경우를 중복 순열의 경우의 수를 만들어 구하였고, 각 벌통의 칸에서 꿀을 퍼갈지 안퍼갈지를 부분집합의 경우의 수를 만들어 구하였다.
N, M이 크지 않은 수로 주어지므로 완전 탐색으로 풀 수 있음을 추측할 수 있다. 로직을 세우고 시간복잡도를 계산해도 문제에서 주어진 시간을 초과하지 않음을 알 수 있다. 설명은 코드에 주석으로 달아놓았다.
소스 코드
def perm(index): # 첫번째 벌꿀통의 r, c 두번째 벌꿀통의 r, c를 중복순열로 생성
if index == 4:
check() # 값을 구하러 간다
return
for i in range(N):
numbers.append(i) # 이번 수를 중복 순열에 넣고
perm(index+1) # 다음 index의 수를 고르러 간다
numbers.pop() # 이번 수를 중복 순열에 넣지 않고 이번 index에 넣을 다음 수를 찾으러 간다
def check():
global answer, max1
a, b, c, d = numbers[0], numbers[1], numbers[2], numbers[3]
if b > N-M or d > N-M: # M칸 크기의 벌꿀 통을 가로줄에 넣을 수 없는 경우 진행하지 않는다
return
selected = [[False for _ in range(N)] for _ in range(N)] # 벌꿀통이 놓인 곳을 표시
subset_selected = [[False for _ in range(N)] for _ in range(N)] # 벌꿀통 안에서 벌꿀을 퍼갈 공간 표시
for i in range(M):
selected[a][b+i] = True # 벌꿀통을 놓았다고 표시한다
max1 = 0
subset(a, b, 0, subset_selected) # 벌꿀통 안에서 퍼간 벌꿀의 양이 C를 넘지 않으면서 최대 가치를 지니는 경우가 언제인지
# 부분집합으로 모든 경우를 만들어서 판단한다
max2 = max1
for i in range(M):
if selected[c][d+i]: # 2번째 벌꿀 통을 놓는데 1번째 벌꿀 통이랑 겹치면 진행하지 않는다
return
selected[c][d+i] = True
max1 = 0
subset(c, d, 0, subset_selected) # 2번째 벌꿀 통 안에서 1번째 벌꿀통 부분집합 만들기에서 했던 것과 동일 행위 진행
answer = max(answer, max1 + max2) # 정답 갱신
def subset(i, j, index, subset_selected): # 부분집합 경우의 수 생성 코드
global max1
if index == M: # 모든 벌꿀통의 칸에 대해 진행했으면
temp = 0
values = 0
for k in range(M):
if subset_selected[i][j+k]: # 선택된 칸의
temp += board[i][j+k] # 양의 누적을 저장하고
values += board[i][j+k]**2 # 가치의 누적을 저장한다
if temp > C: # 양이 C를 넘었으면 담을 수 없으므로 진행하지 않는다
return
max1 = max(max1, values) # 양이 C를 넘지 않았다면 가치 누적값의 최대를 갱신한다
return
subset_selected[i][j + index] = True # 벌꿀통의 특정 칸을 고르는 경우
subset(i, j, index+1, subset_selected) # 재귀 진행
subset_selected[i][j+index] = False # 벌꿀통의 특정 칸을 고르지 않는 경우
subset(i, j, index + 1, subset_selected) # 재귀 진행
T = int(input())
for tc in range(1, T+1):
max1 = 0
N, M, C = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(N)] # 2차원 배열 1줄로 받는 코드
answer = 0 # 정답을 저장할 변수
numbers = [] # 중복순열을 생성할 코드
perm(0) # 중복순열 재귀
print(f"#{tc} {answer}") # 정답 출력
'알고리즘 문제 풀이 > 삼성 Swea' 카테고리의 다른 글
| SWEA 1231 - 중위 순회 [파이썬] (0) | 2023.02.11 |
|---|---|
| SWEA 10726. 이진수 표현 [Java] (0) | 2023.02.04 |
| SWEA 1288. 새로운 불면증 치료법 [Java] (0) | 2023.02.04 |
| SWEA 1954. 달팽이 숫자 [Java] (0) | 2023.01.22 |
| SWEA - 1206. View (0) | 2022.07.24 |
