백준 알고리즘 - 가장 긴 증가하는 부분수열(11053번)[Python]

문제

문제 상황

- 부분 집합 중 증가하면서 길이가 가장 긴 수열을 찾는다

 

해결 전략

- 단순히 어떤 위치에서 대소비교를 통해 길이를 추가하면 여러가지 경우의 수 중 연속적으로 최대의 경우를 찾는게 아니라 정해진 위치보다 작은 수들의 집합을 찾게 된다. 즉, 연속된 증가하는 수열이 아니라 어떤 수보다 작은 수들의 집합을 찾게된다. 그래서 dp를 사용해야 한다. 

잘못된 코드

n, seq = int(input()), list(map(int, input().split()))
dp = [1 for _ in range(n)] # 최소 길이가 1이므로
for i in range(1, n):
    for j in range(i):
        if seq[i] > seq[j] :
            dp[i] += 1
print(dp)

- 이렇게 코딩을 하면 j번째 요소들이 증가하는 수열을 보는 것이 아니라 i번째 요소보다 작으면 무조건 길이를 증가시키기 때문에 ex) 10, 20, 10, 30 의 경우 30에서 길이를 3이 아닌 4로 본다. 

코드 

n, seq = int(input()), list(map(int, input().split()))
dp = [1 for _ in range(n)] # 최소 길이가 1이므로
for i in range(1, n):
    for j in range(i):
        if seq[i] > seq[j] :
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))

해설

손글씨로 이미지 넣기

새로 학습한 것 & 실수

- 강의에서 받은 코드와 if 조건이 다르고 max 안의 비교 조건도 다르다.