Softeer 연습문제(3단계) - 징검다리

Candidate | Softeer Assessment UI

Candidate | Softeer Assessment UI

 

나의 코드

import sys
from collections import deque
input = sys.stdin.readline

max_bg = 0

bg_n = int(input())
bg_info = list(map(int, input().split()))

for start in range(len(bg_info)):
    visit = 1
    queue=deque()
    queue.append([start, visit])
    while queue:
        now_start, visit_ct = queue.popleft()
        visit=max(visit, visit_ct)
        for next in range(now_start+1, len(bg_info)):
            if bg_info[now_start] < bg_info[next]:
                queue.append([next, visit_ct+1])
    max_bg = max(max_bg, visit)
print(max_bg)

 

하지만.,... 메모리 초과 발생.. ㅠㅠ

 

수정된 코드(배운점)

DP 배열을 사용해 비교후 증감해주는 방법

import sys
input = sys.stdin.readline

max_bg = 0

bg_n = int(input())
bg_info = list(map(int, input().split()))

dp_list = [1]*bg_n

#뒤에 꺼랑 비교해서 증감 해줌
for i in range(1, bg_n):
    for j in range(i):
        if bg_info[i]>bg_info[j]:
            dp_list[i]=max(dp_list[j]+1, dp_list[i])
print(max(dp_list))