목록11054 (1)

YoungSoo

백준 - 가장 긴 증가하는 부분 수열, 가장 긴 바이오닉 부분 수열(11053, 11054 파이썬 풀이)

먼저 비교적 쉬운 문제인 가장 긴 증가하는 부분 수열 문제는 한 수열에서 부분적으로 증가하는 수열을 찾고 그 중에 제일 긴 부분 수열을 찾는 문제이다. import sys input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) dp = [0 for i 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라는 배열을 먼저 선언해준 뒤 반복문을 통해 증가하는 부분 수열을 모두 구해준다. 이중 포문을 사용하는 이유는 현재 계산 중인 배열에 해당 조건에..
코딩테스트 2023. 1. 5. 18:02
이전 Prev 1 Next 다음