흰 스타렉스에서 내가 내리지

[BOJ] (DP) 11053번 가장 긴 증가하는 부분 수열 본문

Problem Solving

[BOJ] (DP) 11053번 가장 긴 증가하는 부분 수열

주씨. 2022. 2. 5. 18:15
728x90

 

다이나믹 프로그래밍으로 풀어야 하는 건 알겠었는데, 어떻게 해야될지 좀 헤맸던 문제.

검사할 배열을 1부터 하나하나 늘려가면서, 이케이케

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

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

for i in range(n):
    for j in range(i):
        if arr[j] < arr[i]:
            dp[i] = max(dp[i], dp[j]+1)

print(max(dp))

 

 

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

 

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

 

'Problem Solving' 카테고리의 다른 글

[BOJ] (ALGO) 14003번 가장 긴 증가하는 부분 수열 5 ★  (0) 2022.02.06
[BOJ] (BIT, BF)14391번 종이 조각 ★★  (0) 2022.02.06
[BOJ] (DFS) 1248번 맞혀봐  (0) 2022.02.04
[BOJ] (BF) 14225번 부분수열의 합  (0) 2022.02.02
[BOJ] (DP, BFS)14226번 이모티콘  (0) 2022.02.01
'Problem Solving' Related Articles more