백준 11053 파이썬

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

11053번: 가장 긴 증가하는 부분 수열

 

정답 코드

import sys


N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1] * N
for i in range(N):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j] + 1)
# print(dp)
print(max(dp))

 

 문제 조건(N<=1000) 상 이중for 문을 사용해도 되겠다고는 생각했지만 접근법을 떠올리기 어려운 문제였다.

두 개의 인덱스(i, j) 를 사용하는데, arr[j] 가 arr[i] 보다 앞에 위치(j < i)한다고 생각하면 된다. 구하고자 하는 답은 증가하는 부분 수열의 길이 이므로, 특정 인덱스에서 얼만큼의 길이를 갖는지 별도의 배열에 값을 저장할 수 있다.

 

 이 별도의 배열은 길이가 N 인 dp 라고 정했고, 초기 원소는 모두 1로 갖는다. 자신보다 큰 원소가 없다 하더라도, 자기 자신은 첫번째 순서가 되기 때문에 원소의 값은 모두 1로 초기화 했다.

 

두 인덱스를 for 문으로 순회하며 전후의 원소끼리 대소 비교를 한다.

후자의 원소가 더 크다면, 후자의 인덱스를 가지는 dp 배열의 값을 업데이트 해주는데, 전자의 dp 값 보다 1을 추가하여 비교할 수 있다. 이 때 max() 메소드를 사용하여 dp[i] 의 값을 업데이트 할 수 있다.

 

 

 

다른 정답 코드 (속도 빠름)

def sol(N, seq):
    result = [seq[0]]
    index = 0
    for i in range(1, N):
        if result[index] > seq[i]:
            result.append(seq[i])
            index += 1
        else:
            for j in range(index + 1):
                if result[j] <= seq[i]:
                    result[j] = seq[i]
                    break
    index += 1
    return index


if __name__ == "__main__":
    N = int(input())
    seq = list(map(int, input().split()))
    print(sol(N, seq))