백준(2352 반도체 설계)

06 Jul 2020

문제

입력

---

문제 해설

이 문제를 처음 풀었을 때는, 주어진 예제를 인덱스화해서 딕셔너리로 정렬하였다. 그리고 소팅을 하여 그리디로 문제를 풀었다. 어떻게든 시간을 줄여봐도,,,무적권 시간초과가 떠서 멘붕이 왔었다. 하다가하다가 몰라서 질문게시판을 보니깐 사람들이 LIS(최장 증가수열) 에 대해서 말하고 있었다. 이 알고리즘에 대해서는 다음 포스팅에 게시하도록 하겠다.(나의 아이펜슬이 도착을 한다면.,,,,)
일단 간단한 아이디어는 배열을 돌긴 도는데, 최적화된 배열을 돌면서 들어갈 자리를 찾는다는 것이다. 실패한 코드는 다음과 같다. —–

n = int(input())
port_list = list(map(int, input().split()))
port_dict = {}
for idx, item in enumerate(port_list):
    port_dict[idx] = item-1
ans = 1
max_ans = -1
def solution(nth, p_list):
    global max_ans, n, ans
    now_left = nth
    now_right = p_list[nth]
    if now_left == n-1:
        max_ans = max(max_ans, ans)
        return
    for i in range(now_left+1, n):
        if port_dict[i] > now_right:
            ans += 1
            solution(i, p_list)
            ans -= 1
    
for i in range(n):
    solution(i, port_dict)

print(max_ans)

나름 짧게 짜서 될줄 알았더니 시간초과가 났던 거시다,,,, 내가 생각하기에는 입력값이 4만개가 맥시멈이면, 안될수도 있을 것 같다. 거의 O(n^3)에 수렴할듯한 연산이 포함되있어서다. 다음은 LIS를 적용한 코드이다.

n = int(input())
port_list = list(map(int, input().split()))

def lower_bound(arr, val):
    global ans
    for idx in range(0, len(arr)):
        if idx == len(arr)-1:
            return idx
        if arr[idx] <= val < arr[idx+1]:
            return idx+1
        
tmp_list = [-1]
ans = 0 
for i in range(n):
    if tmp_list[-1] < port_list[i]:
        tmp_list.append(port_list[i])
        ans += 1
    else:
        tmp_list[lower_bound(tmp_list, port_list[i])] = port_list[i]
        
print(ans)

LIS를 모른다고 해도 코드를 보면 어떤식으로 했는지 감이 잡힐 것이다. 다만 위의 방법은 정확히 어떤 배열로 ans가 나왔는지 모른다. 즉, 경로를 찾을 수는 없다는 것이다. 경로를 찾으려면은 최대값일 때의 배열을 저장해준다고 하면 되지만, 이또한 항상 해줘야하는 상황이 발생해서 좋지 않은 결과가 나타날 것이다.
그래도 오늘 LIS를 얻은 것 같아 뿌듯하다. 홓호호