알고리즘/백준
가장 긴 증가하는 부분 수열 4 14002번 백준
글을 쓰는 개발자
2020. 12. 2. 21:22
반응형
문제:www.acmicpc.net/problem/14002
14002번: 가장 긴 증가하는 부분 수열 4
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이
www.acmicpc.net
이 문제는 다른 것이 아닌 파이썬 문법에 대한 부족으로 오래 걸렸다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
import sys
N = int(sys.stdin.readline().rstrip())
quest = [0]+list(map(int,sys.stdin.readline().rstrip().split()))
dp = [0]*1001
li = []
ans=0
li.append([])
li[0].append(0)
for i in range(1,N+1):
dp[i]=1
li.append([])
ans=max(dp[i],ans)
for j in range(1,i+1):
if quest[j]<quest[i]:
if dp[i]<dp[j]+1:
li[i]=list(li[j])
dp[i]=dp[j]+1
ans=max(dp[i],ans)
li[i].append(quest[i])
del li[0]
for i in range(N):
if ans==len(li[i]):
print(ans)
for j in li[i]:
print(j,end=' ')
break
|
cs |
위의 코딩에서 17번 줄을 보면 li[i]=list(li[j]) 이 부분이 있다. 여기서 list를 안해주면 이상하게 li[i].append(quest[i]) 할 때 특정 리스트인 li[i]가 아닌 모든 수열에 동일하게 더해진다. 톱니바퀴 리스트를 쓸 때에는 저런 점을 유의해야겠다.
|
1
2
3
4
5
6
|
[[0], [10]]
[[0], [10], [10, 20]]
[[0], [10], [10, 20], [10]]
[[0], [10], [10, 20], [10], [10, 20, 30]]
[[0], [10], [10, 20], [10], [10, 20, 30], [10, 20]]
[[0], [10], [10, 20], [10], [10, 20, 30], [10, 20], [10, 20, 30, 50]]
|
cs |
이런 식으로 저장이 된다.(list를 감싸 주었을 때)
|
1
2
3
4
5
6
|
[[0], [10]]
[[0], [10, 20], [10, 20]]
[[0], [10, 20], [10, 20], [10]]
[[0], [10, 20, 30], [10, 20, 30], [10], [10, 20, 30]]
[[0], [10, 20, 30, 20], [10, 20, 30, 20], [10], [10, 20, 30, 20], [10, 20, 30, 20]]
[[0], [10, 20, 30, 20, 50], [10, 20, 30, 20, 50], [10], [10, 20, 30, 20, 50], [10, 20, 30, 20, 50], [10, 20, 30, 20, 50]]
|
cs |
리스트를 감싸주지 않았을 때에는 다음과 같이 저장이 된다.
반응형