[파이썬/python] 백준 - 12014 주식

문제

https://www.acmicpc.net/problem/12014

---

문제 설명

1. N일간 총 N개의 주식 가격이 숫자로 주어진다.
2. 총 K번의 주식을 구매하려고 한다.
   1. 주식은 하루에 한 번만 살 수 있다.
   2. 맨 처음을 제외하고는 바로 직전에 주식을 샀을 때보다 가격이 올라갔을 때만 사야 한다.
3. N과 K가 주어졌을 때, 조건에 만족하게 주식을 구매할 수 있는지 여부를 출력한다.

 

---

풀이

총 N개의 데이터가 수열로 주어진다.

N개 중 연속으로 증가하는 K개의 숫자가 존재하는지 문제는 묻고있다.

 

N개중 K개가 증가하는지 확인하려면 매 원소마다 현재 내 앞에 나보다 작은 숫자가 몇개있는지 검사해야 한다.

 

이를 최장 증가 부분 수열(LIS) 알고리즘이라고 부른다.

LIS 알고리즘은 단순히 $N^2$으로 구현하는 방식이 있고, 이분탐색을 응용해서 $NlogN$으로 풀이하는 방식이 있다.

 

나는 빠르게 문제 풀이를 위해, 단순 구현을 통해 문제를 해결했다.

 

1번 원소부터 순차적으로 내 앞에 존재하는 원소들을 비교하며 현재 내가 더 크다면 이전 원소의 배열값에 1을 증가시킨다.

최종적으로 dp배열의 가장 큰 값이 최장 증가 부분 수열의 크기가 될 것이다.

 

1. DP 배열을 1로 초기화한다.
2. 1부터 N까지 기준 원소를 잡는다.
3. 기준 원소 i보다 작은 원소 j를 비교해가며 dp 배열을 갱신한다.
4. 최대 증가 수열 길이를 구한 후 K와 비교한다.

---

코드

import sys
input = sys.stdin.readline

for tc in range(1,int(input())+1):
    N,K = map(int,input().split())
    arr = list(map(int,input().split()))
    res = 1
    dp = [1 for _ in range(N)]

    for i in range(1,N):
        for j in range(i):
            if arr[i] > arr[j]:
                dp[i] = max(dp[j]+1, dp[i])

    if max(dp) < K:
        res = 0
    print(f"Case #{tc}")
    print(res)

---

시간복잡도

• 단순 2차원 반복문을 통한 DP 갱신이다. 즉 $O(N^2) = O(10^8)$의 시간복잡도가 소요된다. 문제의 시간제한은 약 5초이기 때문에 아슬아슬하게 통과했다.