백준 문제 제목은... 가끔 가다 보면 영어를 직역해놓은 느낌이다.

11053: 가장 긴 증가하는 수열

1. 다른 풀이

간만의 백준 풀이로... (자그마치 2주 가량 쉬었다.) 머리에 기름칠을 하고자 오늘은 잠깐 고민하다가 풀이를 봤다. 항상 대단하다고 여기는 분의 블로그로!
https://pacific-ocean.tistory.com/153

import sys

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().strip().split()))

dp = [0 for _ in range(n)]

for i in range(n):
    for j in range(i):
        if a[i] > a[j] and dp[i] < dp[j]:
            dp[i] = dp[j]
    dp[i] += 1

print(max(dp))

깔끔...하다...
입력을 받은 후, dp 문제답게 0 리스트를 만들어준다. 그 다음 n까지 반복문을 돌고, 또 그 안에서도 한 번 더 반복문을 돌아준다. (중첩반복)
이때, 만약 a 리스트 안에 들어있는 숫자 중에서 i가 크고 dp, 즉 i까지 증가하는 수열의 길이 갯수가 작을 때 해당 dp[i]를 dp[j]와 같게 만들어준다.
그리고 if문을 지났든 안지났든, i는 무조건 1 이상의 값을 갖게 되므로 1을 더해준다. 그 이유는,

10(1) 20(2) 10(1) 30(3) 20(1) 50(4)

• 괄호 안은 증가하는 수열의 길이

이라는 수열이 있을 때 해당 수열의 길이는 최소 1이기 때문이다. 더불어 만약 if문을 지났을 경우, j들보다는 i가 크다는 말이기 때문에 1을 더해주어야 한다.

마지막으로 dp 리스트 중 가장 큰 것 (max)를 출력하면 이 문제를 해결된다.

간만의 문제라 기억이... 잘 나지 않았다... 다시 머리에 기름칠을 열심히 하다보면 삐걱거리다가도 어느 순간부터 잘 돌아가겠지!