[백준/25241] 가희와 사직 구장 (Python)

Problem : https://www.acmicpc.net/problem/25241

25241번: 가희와 사직 구장

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 01:18:24

 

---

 

문제 설명

 

 

가희가 응원하고 있는 롯데 자이언츠의 홈 구장인 사직 구장의 무대는 R행 C열로 이루어져 있습니다. 가희는 이 무대에 N명의 아이돌을 배치하려고 합니다. N명의 아이돌은 각각 1번부터 N번까지의 번호를 가집니다.

이 중 3명은 삼총사라고 불립니다. 이들은, 서로가 상하좌우나 대각선 방향으로 인접해 있을 때 고유의 효과를 냅니다.

가희는 사직 구장의 무대에 N명의 아이돌을 적절히 배치해서, 그들의 매력을 최대치로 하고 싶습니다. 어떻게 하면 좋을지 알려주세요.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 R과 C와 N이 공백으로 구분되어 주어집니다.

두 번째 줄에 삼총사의 번호 a1, a2, a3이 공백으로 구분되어 주어집니다.

세 번째 줄에 번호가 a1인 아이돌과 번호가 a2인 아이돌이 인접해 있을 때, 번호가 a2인 아이돌과 번호가 a3인 아이돌이 인접해 있을 때, 번호가 a1인 아이돌과 번호가 a3인 아이돌이 인접해 있을 때 추가로 올라가는 매력도가 공백으로 구분되어 주어집니다.

다음 R개의 줄에는 C개의 수가 공백으로 구분되어 주어집니다. r번째 줄의 c번째 수는 r행 c열에 아이돌이 있을 때 올라가는 매력을 의미합니다.

 

출력

 

가희가 N명의 아이돌을 무대에 올렸을 때, 얻을 수 있는 매력의 최댓값을 출력해 주세요.

 

입력 예시

 

1 5 3
1 2 3
999 999 999
99 1 99 1 99

 

출력 예시

 

2197

 

 

---

 

풀이

 

총 3명을 먼저 브루트포스로 배열해보자(3명은 인접하였을 시에 시너지가 있으므로). R*C <= 200이고, 이 중 순서 상관 없이 정하는 경우의 수는 C(R*C, 3)이므로 총 O((R*C)^3)의 시간복잡도를 지닌다.

 

나머지는 정렬을 통해 그리디하게 매력도가 높은(값이 큰) 값을 지니게 할 수 있다. N명을 그리디하게 우선 선발해주자.

 

• 이 삼총사가 N개의 그리디 값에 포함된다면 : 인접 여부를 통한 값만을 더해주면 된다.
• N개의 그리디 값에 일부 이상이 포함되지 않는다면 : 이 역시 그리디하게 가장 작은 값부터 제거하되, 이 값이 삼총사에 해당하는 값이라면 제거한다. 그리고 삼총사에 해당하는 좌표의 값을 더해주도록 하자. 인접 여부를 통한 값 역시 더해줄 필요가 있다.

이 과정은 O(1) 시간복잡도를 지니므로(최대 3명의 교환이 일어난다), 전체 시간복잡도는 그대로 O((R*C)^3)이 된다. 빠르게 풀어볼 수 있겠다.

 

풀이 코드

from itertools import combinations
import sys
input = sys.stdin.readline

R, C, N = map(int, input().split())
_, _, _ = map(int, input().split())
synergy = sorted(map(int, input().split()), reverse = True)
maps = [list(map(int, input().split())) for _ in range(R)]
maps = [(maps[r][c], r*C+c) for r in range(R) for c in range(C)]
sorted_maps = sorted(maps, reverse=True)
used_set = set()
used_sum = 0
for i in range(N) :
  used_set.add(sorted_maps[i][1])
  used_sum += sorted_maps[i][0]
ans = 0

for combs in combinations(range(R*C), 3) :
  max_adj = 0
  used = []
  unused = []
  for i in range(3) :
    ir, ic = combs[i] // C, combs[i] % C
    jr, jc = combs[(i+1) % 3] // C, combs[(i+1) % 3] % C
    if abs(ir - jr) + abs(ic - jc) == 1 or abs(ir - jr) == abs(ic - jc) == 1 :
      max_adj += 1
    if combs[i] not in used_set :
      unused.append(combs[i])

  sums = used_sum + sum(synergy[:max_adj])
  idx, cnt = N-1, 0
  while cnt < len(unused) :
    if sorted_maps[idx][1] in combs :
      idx -= 1
      continue
    sums += maps[unused[cnt]][0] - sorted_maps[idx][0]
    idx -= 1
    cnt += 1

  ans = max(ans, sums)
print(ans)

풀이 완료!