글 읽기 - 시간초과 질문 있습니다..

ajm0924 2년 전 0

아무리 시간초과를 막으려고 해봐도 여기까지가 최선인데 이 방법은 백트래킹이라서 시간초과가 나는 건가요..?

그렇다면 이 문제를 동적 계획법으로 접근하려면 어떻게 접근해야하나요..?

import copy
import sys

num = int(input())

answer = 1000000
cost = 0
cost_list = []
answer_list = []

for i in range(num):
  add_list = list(map(int, sys.stdin.readline().split()))
  cost_list.append(add_list)

num_list = []
add_num_list = []

def make_num():
  global num_list
  global cost
  global cost_list
  global answer
  global answer_list
  count = 0
  if len(add_num_list) == num:
    for i in add_num_list:
      cost = cost + cost_list[count][i]
      count = count + 1
      if cost >= answer:
        count = 0
        cost = 0
        break
      if count == num:
        if cost <= answer:
          count = 0
          answer = copy.deepcopy(cost)
          cost = 0
          continue
    return
  
  for i in range(3):
    if add_num_list == []:
      add_num_list.append(i)
      make_num()
      add_num_list.pop()
    else:
      if add_num_list[-1] == i:
        continue
      add_num_list.append(i)
      make_num()
      add_num_list.pop()

make_num()
print(answer)

# 39 32 63 29 11 13 47 19 / 1 0 2 1 2 1 0 2

ksi4495 2년 전 2

3^N 꼴이라 백트래킹으로 하면 시간이 너무 오래 걸립니다.

i번째 집에 j색깔을 칠했을 때의 최댓값을 구하는 방향으로 가시면 될 것 같습니다.

0000000000 2년 전 0

@ksi4495 최댓값이요...?

ksi4495 2년 전 0

잘못 적었네요. 최솟값이 맞습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 질문 있습니다..

ajm0924 2년 전 0

ksi4495 2년 전 2

0000000000 2년 전 0

ksi4495 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말