-
[BOJ/Python] 백준 11052 - 가장 긴 증가하는 수열Solve 2024. 7. 8. 15:56
문제
https://www.acmicpc.net/problem/11053
더보기문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
풀이
N = int(input()) A = list(map(int, input().split())) dp = [1] * N for i in range(1, N): # 배열 A의 각 요소 순회, 현재 i for j in range(i): # i 이전의 값 순회 if A[i] > A[j]: dp[i] = max(dp[i], dp[j] + 1) # dp[j] + 1은 A[j]까지의 최장 증가 부분 수열의 길이에 A[i]를 추가한 길이 print(max(dp))
- 수열의 길이를 입력받을 리스트 dp를 생성한다.
원소가 1개만 있어도 길이는 1이므로 1로 초기화한다. - 입력받은 배열의 요소를 순회하면서 -> 해당 요소 이전의 값을 반복 순회하고 이동한다.
- 현재 인덱스(i)의 값보다 j가 작은 경우,
인덱스의 길이는 현재 길이 혹은 현재 순회중인 값의 길이에 인덱스 길이를 추가한 것 중 큰 값을 선택한다.
풀이 기반 예시
- input: 10 20 10 30 20 50 - 초기화: dp = [1, 1, 1, 1, 1, 1] i = 1, j = 0: A[1] > A[0] → dp[1] = max(1, 1 + 1) → dp = [1, 2, 1, 1, 1, 1] i = 2, j = 0, 1: A[2] <= A[0], A[2] <= A[1] → dp = [1, 2, 1, 1, 1, 1] i = 3, j = 0, 1, 2: A[3] > A[0] → dp[3] = max(1, 1 + 1) → dp = [1, 2, 1, 2, 1, 1] A[3] > A[1] → dp[3] = max(2, 2 + 1) → dp = [1, 2, 1, 3, 1, 1] i = 4, j = 0, 1, 2, 3: A[4] > A[0] → dp[4] = max(1, 1 + 1) → dp = [1, 2, 1, 3, 2, 1] i = 5, j = 0, 1, 2, 3, 4: A[5] > A[0] → dp[5] = max(1, 1 + 1) → dp = [1, 2, 1, 3, 2, 2] A[5] > A[1] → dp[5] = max(2, 2 + 1) → dp = [1, 2, 1, 3, 2, 3] A[5] > A[3] → dp[5] = max(3, 3 + 1) → dp = [1, 2, 1, 3, 2, 4]
'Solve' 카테고리의 다른 글
[BOJ/Python] 백준 2644 - 촌수계산 (4) 2024.07.22 [BOJ/Python] 백준 2805 - 나무 자르기, 백준 1654 - 랜선 자르기 (0) 2024.07.15 [BOJ/Python] 백준 1874 - 스택 수열 (0) 2024.07.08 [BOJ/Python] 백준 11724 - 연결 요소의 개수 (0) 2024.07.08 [BOJ/Python] 백준 1012 - 유기농 배추 (0) 2024.07.08 - 수열의 길이를 입력받을 리스트 dp를 생성한다.