99클럽 코테 스터디 30일차 TIL : 백준 1965번, 최장 증가 부분 수열

 

1. 오늘의 문제

 

오늘의 문제는 최장길이 부분수열의 변형이다.

 

이 문제는 유형이 달라도 거의 복붙이라 별로 어렵지 않음.

 

문제

 

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법은 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

 

2. 코드

 

from sys import stdin
put = stdin.readline

num = int(put())
boxs = list(map(int, put().split()))
inners = [1 for _ in range(num)]

for i in range(num):
    for j in range(0,i):
        if boxs[i] > boxs[j] :
            inner = inners[j] + 1
            inners[i] = max(inners[i], inner)
print(max(inners))

 

3. 느낀점

 

각 값을 비교하고, 현재 값이 이전 값보다 크면 이전 값에다가 꼬리를 붙인다고 생각하니 쉽게 풀린다.

 

알고리즘 자체도 한번만 이해하고 나면 구현하기도 무척 쉽다.

 

오늘은 문제 풀고 올리는데 까지 10분도 걸리지 않았다.

 

하나를 완벽하게 익혀서 뿌듯한 하루이다.