문제
https://www.acmicpc.net/problem/1965
풀이
최대 상자의 개수를 구하려면 다이나믹 프로그래밍을 활용한 최장 증가 부분 순열을 구현하면 된다.
전체 상자의 개수만큼 1로 이루어진 배열 dp를 생성한다.
두 번째 수부터 검사를 시작한다.
자신(i)보다 앞에 있는 수들(j) 중 작은 것이 있다면,
자신(i)의 dp와 해당 수(j)의 위치에 저장된 dp값 + 1을 비교하여 더 큰 값으로 갱신한다.
이중 반복문을 모두 돌면 dp에 저장된 값들 중 최댓값이 정답이 된다.
코드
import sys
input = sys.stdin.readline
n = int(input())
li = [*map(int, input().split())]
dp = [1] * n
for i in range(1, n):
for j in range(i):
if li[i] > li[j]:
dp[i] = max(dp[i], dp[j] + 1)
print(max(dp))
'Koala - 12기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/phthon3] 9251번: LCS (0) | 2023.09.18 |
---|---|
[백준/Python] 15486번 : 퇴사 2 (0) | 2023.09.18 |
[프로그래머스/Java] 이모티콘 할인행사 (0) | 2023.09.17 |
[백준/python3] 1463번 : 1로 만들기 (0) | 2023.09.17 |
[백준/C++] 25706번: 자전거 묘기 (0) | 2023.09.17 |