백준 14002 파이썬

https://www.acmicpc.net/problem/14002

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

코드

n = int(input())
a = list(map(int,input().split()))

dp = [0] * n
box = []

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
    
chk = max(dp)
print(chk)

for i in range(n - 1, -1 ,-1):
    if dp[i] == chk:
        box.append(a[i])
        chk -= 1
box.reverse()
print(*box)

---

해설

 

dp 즉 다이내믹 프로그래밍을 활용한 문제이다. 첫 번째 2중 for문을 이용해 가장 긴 증가하는 부분 수열을 구할 수 있다.

 

입력값

6 10 20 10 30 20 50

를 입력한다고 가정해보자.

 

이렇게 입력하면 dp값은 

dp = [1, 2, 1, 3, 2, 4] 로 저장이 된다.

 

dp에서 1,2,3,4순서대로 a[]에 대응시켜 출력시키면 된다는 생각이 들 것이다.

 

방법은 n - 1부터 -1 까지 -1씩 감소시키는 for문을 이용하는 것이다. chk라는 변수에 max(dp) 위 예시에서는 4를 넣어주고 dp[i]가 chk와 일치하면 box라는 빈 공간에 a[i] 값을 입력받는다.

 

그리고 입력받게 되면 chk를 -1 해준다.  for문을 다 돌고나면 box = [50, 30, 20, 10]이 입력이 될 것이다. 값이 거꾸로 되어있기 때문에, reverse() 함수를 이용하고 출력한다.

 

print(box)를 하게 되면 [10, 20, 30, 50]이 출력 된다. 하지만 이대로 답 제출을 하게 되면 틀렸다고 나오는데, 바로 괄호가 같이 입력되기 때문이다. 

 

괄호를 없애는 방법은 *을 이용하는 것이다. 파이썬에서는 * 연산자를 통해서 객체의 압축을 풀 수 있다. 여기서는 대괄호를 없애준다.

 

 

 

관련 문제

• 11053번. 가장 긴 증가하는 부분 수열
• 11055번. 가장 큰 증가 부분 수열
• 11722번. 가장 긴 감소하는 부분 수열