코딩테스트

[백준] 1965번 상자넣기 - Python

CuckooBird 2023. 2. 19. 22:00

백준 실버3 1965번 상자넣기 - Python

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

 

1965번: 상자넣기

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가

www.acmicpc.net


문제


코드

맞았습니다가 뜬 코드입니다. - 메모리 31256KB | 시간 228ms | 코드 길이 251B

import sys
input = sys.stdin.readline
N = int(input().rstrip())
box = list(map(int, input().rstrip().split()))
dp = [1] * N
for i in range(1, N):
    for j in range(i):
        if box[i] > box[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

 

dp에는 N길이 만큼의 1을 저장해둡니다. 모든 상자는 자기자신을 포함하기 때문입니다.

 

이중for문을 이용하여 i에는 뒤에 있을 상자를, j에는 앞에 있을 상자를 나타냅니다.

 

뒷 상자에 넣을 수 있는 상자의 개수(dp[i])와 앞 상자에 넣을 수 있는 상자의 개수(dp[j]) 중 큰 값이 i번째 상자에 들어갈 수 있는 상자의 개수가 됩니다.


Search 🔍


후기

다른 분의 코드를 베껴서.. 좀 죄책감이 있긴 합니다..

 

실버2..???