[CodeUp/3515] 사탕 줍기 2 (python)

Problem : https://codeup.kr/problem.php?id=3515
Status : solved
Time : 00:16:41

 

 

 

---

문제 설명

 

 

지원이는 사탕을 사기위해 새로 개업한 사탕가게에 갔다.
사탕가게 아저씨는 격자판에 사탕을 각각 담아 두고, 첫 손님 기념으로 다음과 같은 제안을 하였다.

 

"각 행과 열에 여러개의 사탕이 있는데, 각 행과 열이 겹치지 않게 사탕을 가져가라. "

 

즉, 1행 1열을 선택했다면 2행 부터는 1열을 선택하지 못한다.

지원이는 머리를 써서 최대한 많은 수의 사탕을 가지고 싶어한다.

지원이가 가질 수 있는 최대 사탕수를 구하시오.

 

 

예)

3	1	4
2	5	4
1	4	1

 첫 행에 3, 둘째 행에 4, 셋째 행에 4를 선택하면 최대 사탕수는 11이 된다.

 

 

입력 및 출력

 

입력

 

첫 행에 격자판의 크기 N이 입력된다.(N<=10)

둘째 행부터 N+1행까지 격자판의 정보인 사탕수가 입력된다.

 

출력

지원이가 가질 수 있는 최대 사탕수를 출력한다.

 

 

입력 예시

 

3 3 1 4 2 5 4 1 4 1

 출력 예시

11

 

 

---

 

풀이

 

사족을 붙이자면 재활치료(?) 겸 푼 첫 문제인데, 예상보다 시간이 오래 걸려 당황했다.

 

핵심은 N개의 열을 각각 1번만 방문하는 것이라고 볼 수 있다.

 

• N이 10개 이하의 수이므로, 가급적 완전 탐색을 실행하는 것이 좋다.
• 하지만 파이썬은 매우 느린 언어로 완전탐색을 통해 풀이하게 되면 무조건 시간 초과가 난다. (반례 : N = 10이고 격자의 모든 값이 1인 경우를 생각해보면, 10!번의 탐색을 진행해야 한다. 우리 파이썬은 시간내에 그런거 못한다)
• 따라서 Dynamic Programming을 적용해 풀이해볼 필요가 있다.

 

구체적으로 N = 7인 다음과 같은 상황을 가정하자.

1~3행에서 1~3열을 방문했다는 상황을 가정하자.

그렇다면 4~7행에서는 4~7열의 조합 중 가장 큰 사탕을 고르는 경우가 정답이 되고, 1~3행에서도 역시 1~3열에서의 조합 중 가장 큰 사탕을 고르는 경우가 정답이 된다. 즉 전체 문제를 각 행에서의 부분문제로 쪼갤 수 있다고 본다.

 

즉, 3행에서 1~3열을 방문했을 때의 최댓값만을 생각하면 되며, 그 이외의 경우는 계산하지 않고 넘길 수 있다!

 

 

구체적으로는 다음 흐름대로 진행하였다.

1. 열을 방문한 모든 경우의 수의 MAX를 저장하는 리스트를 생성한다.
2. 큐(라고 표현하였지만 사실 스택)에서 (현재까지의 사탕 수, 방문한 행, 현재 열 인덱스)를 가져온다.
3. 다음 열에서 방문할 수 있는 행을 조사한다.
   1. 만약 지금까지의 열에서 방문하지 않은 행이며
   2. 이 행을 방문하였을 때 사탕 수가 최대가 된다면
   3. MAX를 저장하는 리스트에 최대 사탕 수를 Update하고, (다음 사탕 수, 새로운 방문한 행, 다음 열 인덱스)를 큐에 삽입한다.
4. 이를 큐가 바닥날때까지 반복한다면, MAX를 저장하는 리스트의 가장 끝 값(모든 행을 방문한 경우)에 정답이 저장된다.

 

 

 

풀이 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline

N = int(input())
num_list = [list(map(int, input().split())) for _ in range(N)]
max_list = [-1]*( 1 << N )


q = [(0, 0, 0)]

while q :
  tot_num, visited, idx = q.pop()
  if idx == N :
    continue

  for i in range(N):
    new_visited = visited | ( 1 << i )
    if new_visited != visited and max_list[new_visited] < tot_num + num_list[idx][i]:
      max_list[new_visited] = tot_num + num_list[idx][i]
      q.append((tot_num + num_list[idx][i], new_visited, idx+1))

print(max_list[-1])

 

생각보다 쉬운 문제인데 생각보다 더 오래 걸렸다. 재활치료가 더 필요할 듯 싶다!

풀이 완료!