알고리즘

[백준] 1965 상자넣기 - 실버 2

swanzzz 2025. 6. 1. 23:24
반응형

[오늘의 문제]

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

[오늘의 학습 키워드]

  • DP
  • 구현

1. 문제설명

 

일렬로 늘어선 상자에 순서대로 상자를 넣습니다.

 

왼쪽에 있는 상자가 오른쪽에 있는 상자들 중 하나에 들어갈 수 있는데 상자는 크기가 달라서 자신보다 크기가 큰 상자에만

 

들어갈 수 있습니다.

 

1 5 2 3 7 크기의 상자가 늘어선 경우 1 2 3 7 순서로 상자를 넣는다면 최대 4개의 상자를 넣을 수 있죠

 

이런 방식으로 상자의 크기가 주어질 때, 한번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 만들어야 합니다.

[제한사항]

  • 시간 제한 2초
  • 메모리 제한 128MB
  • 1 ≤ N ≤ 1000

2. 접근방식

 

문제가 저번에 풀었던 가장 긴 증가하는 부분 수열 문제와 비슷합니다.

 

현재 상자를 기준으로 이전의 상자들 가운데 들어갈 수 있는 최대의 상자 개수를 넣어주면 되겠죠

 

동일하게 기준값과 비교값을 토대로 접근해 보았습니다.

 

 

손으로 먼저 풀어보았습니다.

 

기준값과 비교값을 토대로 현재의 기준값이 비교값보다 큰 경우 DP값 중 더 큰 값을 현재의 값에 넣어줍니다.

 

 

이렇게 보죠

 

3의 상자에 들어갈 수 있는 최대의 값을 찾는 상황이라고 생각해 보겠습니다.

 

중첩 반복문을 통해 기준값 i와 비교값 j를 설정해준 경우로 보겠습니다.

 

현재 i는 4번째 값을 탐색중입니다. 그렇다면 j의 범위는 0부터 2까지가 되겠죠

 

비교값이 1인 경우를 보죠 

 

기준값 3이 더 크므로 DP의 현재값이 바뀌어야 합니다.

 

DP[i] 는 초기화된 기존값이 들어온 상태일 것입니다.

 

상자의 크기는 1000을 넘지 않는 자연수라고 했으니 최소 1개의 상자가 들어갈 수 있습니다.

 

그러니 DP 테이블은 우선 1로 초기화 된 상태라고 보고 기준값까지 반복이 실행되어 DP 값이 채워진 상태로 보겠습니다.

 

이때 1은 3의 상자에 들어갈 수 있습니다. 그렇다면 DP[i] 값이 바뀌어야 겠죠

 

DP[i] 값을 바꾸기 위해선 DP의 이전값과 비교해 주어야 하는데 1에 들어간 상자들이 있을 테니 1 상자의 DP 값  DP[j]의 값에

 

3의 상자에 들어가니 1이 늘어나죠

 

따라서 최종적으로 비교하는 코드는 DP[i] = max(DP[i], DP[j] + 1) 로 비교하게 되겠죠

 

여기선 당연히 DP j 값이 더 크기 때문에 DP[i] 값이 바뀌게 될 것입니다.

 

그럼 DP 값을 바꿔주고 j값이 바뀌기 때문에 다음 값과 비교하게 되죠 

 

여기선 boxes의 비교값이 기준값보다 크기 때문에 상자에 들어갈 수 없죠

 

여긴 건너뛰어야 합니다.

 

다음은 여길 비교하게 되겠죠 

 

기준값이 더 크기 때문에 비교값에 들어간 상자를 포함해서 3에 상자가 들어갈 수 있습니다.

 

따라서 동일한 비교를 거치면 DP[i] 는 현재 2이고 DP[j] 는 총 3이 되기 때문에 DP[i] 값이 바뀌게 되겠죠

 

모든 동작이 완료되면 3은 

 

 

이렇게 총 3이 되고 종료되겠죠

 

이걸 7까지 반복하면 결국 7의 DP 값은 4가 되겠죠

 

 

이 동작을 코드로 구현해 보았습니다.

3. 코드

import sys
input = sys.stdin.readline

# 입력
N = int(input())
boxes = list(map(int, input().split()))

# DP 테이블 초기화
DP = [1] * N

# 기준값
for i in range(N):
    # 비교값
    for j in range(i):
        # 기준값에 비교값 상자들이 들어올 수 있는 경우
        if boxes[i] > boxes[j]:
            # 기준값 DP에 더 큰값 넣어주기
            DP[i] = max(DP[i], DP[j] + 1)

# 그중 가장 많은 상자가 들어간 경우 출력
print(max(DP))

[코드설명]

 

앞서 상자의 크기는 1,000 이하의 자연수라고 했으니 모든 상자에는 최소 1개의 상자들이 들어갈 수 있습니다.

 

따라서 DP 테이블을 기본적으로 1로 초기화 시켜주었습니다.

 

그 후 중첩 반복문을 토대로 DP 테이블을 채워갑니다.

 

기준값 i를 설정하고 그 이전값들을 비교하며 상자에 들어갈 수 있는지 여부를 비교해 줍니다.

 

상자에 들어갈 수 있다면 현재 이전에 들어온 값들과, 새롭게 들어오는 값들 중 더 큰 값을 DP에 남겨 놓습니다.

 

이 과정을 반복하여 가장 많은 상자가 들어간 경우를 출력해 주었습니다.

4. 결과

[회고]

 

이번 문제는 쉬웠습니다.

 

문제를 보고 DP의 동작과정중 중첩 반복문이 가장 먼저 떠올랐고

 

이를 토대로 현재 상자에 들어올 수 있는 최대의 경우의 수를 찾아야 겠구나가 생각 났습니다.

 

손으로 여기까지 먼저 작성하였고 그 다음 세부 조건을 찾아 보았습니다.

 

첫번째 반복문을 통해 기준값을 설정해주고 그 이전의 값들을 비교하며 이 값이 나보다 작다면 내 상자에 들어올 수 있는 상자들이구나를 깨닫고 비교값을 설정해 주었습니다.

 

동작과정을 통해 DP를 초기화 시켜주는데 처음에는 DP를 0으로 초기화 시켜주니 원하는 결과에서 1이 모자란 값이 나왔습니다.

 

문제의 조건을 자세히 살펴보니 1,000 이하의 자연수 라고만 적혀 있었기에 최소 1개의 상자가 들어갈 수 있겠구나라고 생각하여 DP를 1로 초기화 하였습니다.

 

다른 방법으로는 0으로 초기화한 다음 처음상자를 1로 초기화하고 점화식을 동작하는 방법도 존재하는데

 

굳이 두 줄의 코드를 작성하기 보다는 처음부터 초기화 하는 방향으로 설정해 주었습니다.

 

그 후 작성한 점화식을 토대로 코드를 동작하였고 원하는 결과를 출력할 수 있었습니다.

 

문제를 풀고나서 이전에 풀었던 문제중 비슷한 문제가 있었던 것 같은데 라는 생각이 들었고

 

이전 블로그글을 찾던 중 가장 긴 증가하는 부분 수열 문제와 비슷한 문제인 것을 알게 되엇습니다.

 

코드역시 조금 다를뿐 핵심로직은 완전히 동일하여 사실상 같은 문제로 봐도 무방했습니다.

반응형