[백준_11053] 가장 긴 증가하는 부분 수열

문제 보기: https://www.acmicpc.net/problem/11053

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

풀이 과정

처음에는 코드 2의 방식으로 생각하고 풀이를 해보았습니다.

큰 수를 배열에 저장하면서 그 수를 비교하는 방식으로 전체를 순회하면서 알아보는 방식을 생각하였지만 증가하는 부분 수열을 만드는 다른 경우의 수를 커버하지 못하는 것이 이유인지 틀렸다는 결과만 얻게 되었습니다.

하여 코드 1번의 방식으로 바꾸어서 해결

1. 2중 for문을 이용하여 dp를 업데이트합니다. i까지 이전의 dp를 이용해서 업데이트하고 i를 늘려가면서 갱신한다.

2. 마지막으로 dp의 값중 가장 큰 값을 출력

 

코드

코드 1

import sys

N = int(input())
arr = list(map(int, sys.stdin.readline().split()))
dp = [1] * N

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

print(max(dp))

 

코드 2

N = int(input())
num = list(map(int, input().split()))

max = num[0]
lst = []
lst.append(max)

for i in range(len(num) - 1):
    if max < num[i + 1]:
        max = num[i + 1]
        lst.append(max)

print(len(lst))