글 읽기 - 가지치기 조언 구합니다.(주석 있음)

huozuyinshua 2년 전 0

시간초과 입니다. 가지치기 조언 구합니다

import math
import sys
import heapq

n = int(input())

lt = [int(x) for x in input().split()]

plus,minus,mul,div = [int(x) for x in input().split()]

subState = [0]*(n-1)

minVal = math.inf
maxVal = -math.inf
# 백트래킹 
def findsubstate(subState,now):
    global plus,minus,mul,div
    global minVal,maxVal
    # find solution
    if now == n-1:
        res = 0
        for i in range(n-1):
            if i == 0:
                if subState[i] == 1:
                    res = lt[i]+lt[i+1]
                elif subState[i] == 2:
                    res = lt[i] - lt[i + 1]
                elif subState[i] == 3:
                    res = lt[i] * lt[i + 1]
                elif subState[i] == 4:
                    res = lt[i] // lt[i + 1]
            else:
                if subState[i] == 1:
                    res += lt[i+1]
                elif subState[i] == 2:
                    res -= lt[i+1]
                elif subState[i] == 3:
                    res *= lt[i+1]
                elif subState[i] == 4:
                    res //= lt[i+1]
        minVal = min(minVal,res)
        maxVal = max(maxVal,res)
    else:
        #select and try next step
        for i in range(plus):
            subState[now] = 1
            plus-=1
            findsubstate(subState, now+1)
            subState[now] = 0
            plus += 1
        for i in range(minus):
            minus -= 1
            subState[now] = 2
            findsubstate(subState, now+1)
            subState[now] = 0
            minus += 1
        for i in range(mul):
            mul -= 1
            subState[now] = 3
            findsubstate(subState, now+1)
            subState[now] = 0
            mul += 1
        for i in range(div):
            div -= 1
            subState[now] = 4
            findsubstate(subState, now+1)
            subState[now] = 0
            div += 1

findsubstate(subState,0)

print(maxVal)
print(minVal)

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

문제

문제

출처

ICPC

가지치기 조언 구합니다.(주석 있음)

huozuyinshua 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말