[💕 백준] 11053번. 가장 긴 증가하는 부분 수열

QUESTION.

www.acmicpc.net/problem/11053

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

 

ANSWER. 

import sys

t = int(input()) # 입력 받기
a = [1] * t # 본인 포함하기 위해 1로 시작
l = list(map(int, input().split())) # 수열 입력 받기

for i in range(1,len(l)):
  for j in range(0, i):
    if l[i] > l[j]: # 만약 I가 J보다 크면 
      a[i] = max(a[i], a[j]+1)  # 현재 값과 J+1 한 거랑 비교해서 더 큰 값

print(max(a)) # 가장 많은 부분 수열 출력

 

문제를 이해하기 조금 어려웠던 문제... (테스트케이스 더 찾아서 품)

문제를 좀 더 간단하게 풀이하면.. 다음과 같은 수열이 있을 때!

10

20

10

30

20

50

리스트 a의 값은

1

2

1

3

2

4

가 된다!

 

즉, 본인의 앞에 있는 본인보다 작은 값을 중복없이 세는 것! (본인의 count도 포함이 된다.)

 

그래서 

l[0] 10인 경우) 10보다 작은 값은 없기 때문에 본인만 카운트해서 1

l[1] 20인 경우) 본인보다 작은 값 10이 존재하고, 본인 카운트해서 2

l[2] 10인 경우) 본인보다 작은 값은 존재하지 않기 때문에 본인만 카운트

l[3] 30인 경우) 본인보다 작은 값은 10, 20, 10이 존재하나 중복없이 10, 20만 세서 2 + 본인 카운트 = 3 

l[4] 20인 경우) 본인보다 작은 값은 10, 그리고 본인 카운트 = 2

l[5] 50인 경우) 본인보다 작은 값 10 20 30, 그리고 본인 = 4

최종적으로 4를 출력하게 된다.

 

for문을 두 번 돌려 변수 i는 본인, j는 본인보다 앞에 있는 수들을 출력한다.

그리고 i가 더 클 경우 카운트를 해야하는데, a[i], a[j]+1를 비교해준 이유는

예를 들어 i가 50일 경우, 그 앞에 가장 큰 값인 30에서 +1만 해주면 되기 때문이다.