글 읽기 - 이 문제 백트래킹으로는 풀 수 없나요?

van133 1년 전 0

시간초과가 나오네요...

풀이는 맞게 한것 같은데..

import sys
sys.setrecursionlimit(10**9)
global result
result =0
def dfs(graph,t,start=0,cnt=0,peak=False,last = 0):
    global result
    if cnt>result:
        result=cnt
    if t-start+1+cnt <result:
        return
    if start ==t+1:
        return
    
    for i in range(start,t):
        if peak == True:
            if last>graph[i]:
                dfs(graph,t,i+1,cnt+1,True,graph[i])
        else:
            if  not cnt or last<graph[i] :
                dfs(graph,t,i+1,cnt+1,True,graph[i])
                dfs(graph,t,i+1,cnt+1,False,graph[i])






t = int(input())
graph = list(map(int,input().split()))
dfs(graph,t)
print(result)

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

문제

문제

출처

ICPC

이 문제 백트래킹으로는 풀 수 없나요?

van133 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말