[백준/파이썬][Gold V] 개업 - 13910

[Gold V] 개업 - 13910

문제 링크

성능 요약

메모리: 110908 KB, 시간: 256 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 2월 8일 03:04:36

문제 설명

해빈이는 짜장면을 정말 좋아한다. 짜장면을 너무 좋아한 나머지 짜장면만 파는 중국집을 개업했다! 해빈이는 양손잡이여서 동시에 두 개의 웍(중국 냄비)을 사용하여 요리할 수 있다. 그러나 해빈이는 낭비를 매우 싫어하기 때문에 요리 할 때, 필요 이상 크기의 웍을 사용하지 않으며, 주문 받은 짜장면의 그릇 수에 딱 맞게 요리한다.

<웍>

예를 들어 짜장면 4그릇을 주문 받았는데 5그릇 이상을 요리하지 않으며, 4그릇을 요리할 수 있는 웍에 3그릇 이하의 요리를 하지 않는다.

해빈이가 5그릇을 주문 받았고, 해빈이가 가지고 있는 웍의 종류가 1, 3그릇 용이라면 처음에 1,3그릇용 웍을 동시에 이용하여 4그릇을 만들고 다음 1그릇용 웍을 이용하여 1그릇을 만들어 총 5그릇을 두 번의 요리로 만들 수 있다.

해빈이가 주문 받은 짜장면의 수와 가지고 있는 웍의 크기가 주어질 때, 최소 몇 번의 요리로 모든 주문을 처리할 수 있는지 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 해빈이가 주문 받은 짜장면의 수N(1≤N≤10,000)과 가지고 있는 웍의 개수 M(1≤M≤100)이 주어진다. 두 번째 줄에는 웍의 크기 S_i(1≤S_i≤N)이 M개가 주어지며 같은 크기의 웍을 여러 개 가지고 있을 수 있다.

출력

해빈이가 모든 주문을 처리하기 위해 해야 하는 최소 요리 횟수를 출력한다. 만약 모든 주문을 처리 할 수 없는 경우 -1을 출력한다.

풀이

def main() :
    # 주문 받은 짜장면, 웍 개수
    N, M = map(int, input().split())
    # 웍 용량 리스트
    S = list(map(int, input().split()))

    # 한 번의 요리에서 만들 수 있는 후보 요리량을 구함
    # 단, 웍 하나만 사용할 경우와 두 웍을 같이 사용할 경우 모두 고려
    candidates = set()

    # 1. 단일 웍 사용 : 각 웍의 용량이 후보가 됨 (N보다 작거나 같아야 함)
    for s in S :
        if s <= N :
            candidates.add(s)

    # 2. 두 웍 동시에 사용 : 서로 다른 두 웍의 합 (같은 웍이 두 개 있는 경우도 i < j 로 처리됨)
    for i in range(M) :
        for j in range(i+1, M) :
            sum_val = S[i] + S[j]
            if sum_val <= N :
                candidates.add(sum_val)

    # 후보를 리스트로 변환
    candidates = list(candidates)

    # dp[i]는 i그릇을 만드는 데 필요한 최소 요리 횟수를 차감
    # 초기값은 0그릇을 만드는 데 0회 요리 => dp[0] = 0, 나머지는 아직 만들지 못한 상태로 -1로 표기.
    dp = [-1] * (N + 1)
    dp[0] = 0

    # dp 전이 : 0부터 N까지 가능한 그릇 수에 대해 후보 요리량을 더해 나감.
    for i in range(N + 1) :
        if dp[i] == -1 :    # i그릇을 만들 수 없다면 넘어감
            continue
        # 각 후보 요리량 c를 이용해서 i + c그릇을 만드는 경우를 고려
        for c in candidates :
            if i + c <= N :
                # 아직 i+c그릇을 만드는 최소 횟수를 기록하지 않았거나, 더 적은 요리 횟수를 발견한 경우 갱신
                if dp[i + c] == -1 or dp[i + c] > dp[i] + 1 :
                    dp[i + c] = dp[i] + 1

    print(dp[N])
main()

문제 재정리

• 문제 상황:
  해빈이는 주문받은 짜장면 N그릇을 만들어야 하고, 한 번 요리할 때 동시에 2개의 웍(또는 1개의 웍만 사용)을 사용할 수 있습니다.
  각 웍은 정해진 그릇 수만큼만 요리할 수 있으므로, 낭비 없이 정확하게 요리해야 합니다.
• 사용 가능한 행동:
  한 번의 요리에서 사용할 수 있는 웍 조합은 다음과 같습니다.
  1. 단일 웍 사용: 한 개의 웍을 사용해서 그 웍의 용량만큼 요리
  2. 두 웍 동시 사용: 서로 다른 두 웍을 동시에 사용해서 두 웍 용량의 합만큼 요리
• 문제 목표:
  위 행동들을 적절히 조합하여 총 N그릇을 정확히 만들어내는데 필요한 최소 요리 횟수를 구하는 것입니다.

---

접근 아이디어

문제를 “동전 거스름돈 문제(coin change problem)”처럼 생각할 수 있습니다.

• 동전(코인): 한 번의 요리에서 만들 수 있는 그릇 수(후보 요리량)
• 목표: 총 N그릇
• 조건: 각 요리에서는 후보 요리량(동전)을 한 번 사용한다.

즉, “0그릇에서 시작해서 후보 요리량을 더해가며 N그릇에 도달하는 데 필요한 최소 동전(요리) 개수를 찾는다”는 문제로 볼 수 있습니다.

---

1. 후보(요리량) 목록 구성

1) 단일 웍 사용

• 설명:
  각 웍은 정해진 용량을 가지고 있으므로, 한 번에 한 웍을 사용하면 그 웍의 용량만큼 짜장면을 만들 수 있습니다.
• 예시:
  웍의 용량이 [1, 3]이라면, 후보는 1과 3이 됩니다.

2) 두 웍 동시 사용

• 설명:
  두 개의 웍을 동시에 사용하면, 두 웍의 용량을 합한 그릇 수 만큼 만들 수 있습니다.
  단, 같은 웍을 두 번 사용하려면 해당 웍이 두 개 이상 있어야 하므로, 인덱스가 다른 두 개를 선택하는 방식으로 진행합니다.
• 예시:
  위 예시 [1, 3]의 경우, 두 웍을 동시에 사용하면 1 + 3 = 4그릇이 됩니다.

3) 후보 목록 구성 시 주의사항

• 중복 제거:
  여러 조합으로 같은 그릇 수가 나올 수 있으므로, 후보는 중복 없이 관리해도 좋습니다.
• N보다 큰 경우:
  만약 한 번의 요리로 만들 수 있는 그릇 수가 N보다 크다면 그 후보는 쓸모가 없으므로 제외합니다.

이 과정을 통해 최종 후보 집합은 예시의 경우 {1, 3, 4}가 됩니다.

---

2. DP 테이블 구성 및 초기화

• DP 테이블 정의:
  dp[i]는 “i그릇을 만드는 데 필요한 최소 요리 횟수”를 의미합니다.
• 초기 상태:
  0그릇을 만드는 데는 아무런 요리도 필요하지 않으므로, dp[0] = 0입니다.
  그 외의 값은 아직 만들지 못했음을 나타내기 위해, 일반적으로 -1 또는 매우 큰 수(예, INF)로 초기화합니다.

---

3. DP 전이 (Transition)

DP 전이 과정은 0그릇부터 N그릇까지 각 상태에 대해 후보(한 번 요리에서 만들 수 있는 그릇 수)를 더해가며 최소 요리 횟수를 갱신하는 방식입니다.

전이 과정 세부 설명

1. 현재 상태 선택:
   예를 들어, 현재까지 i그릇을 만들 수 있다고 가정합시다. 이때 필요한 요리 횟수는 dp[i]에 저장되어 있습니다.
2. 후보 요리량 적용:
   후보 목록의 각 후보 값 c에 대해,
   • 현재 상태 i에서 c를 더하면 총 i+c그릇을 만들 수 있습니다.
   • 이때 i+c가 N 이하라면, dp[i+c]를 min(dp[i+c], dp[i] + 1) (만약 아직 기록이 없다면 dp[i+c] = dp[i] + 1)로 갱신합니다.
   이는 “현재까지 i그릇 만드는 데 dp[i]번 요리했고, 한 번 더 요리해서 c그릇을 만들면 dp[i]+1번의 요리로 i+c그릇을 만들 수 있다”는 의미입니다.
3. 모든 상태에 대해 반복:
   0부터 N까지 순차적으로 dp 값을 갱신합니다.
   최종적으로 dp[N]에 N그릇을 만들기 위한 최소 요리 횟수가 기록됩니다.
4. 불가능한 경우 처리:
   만약 dp[N]이 여전히 초기값(-1)이라면, N그릇을 정확히 만들 수 없다는 뜻이므로 -1을 출력합니다.

---

4. 전체 코드 구조

전체 코드는 다음과 같은 구조로 구성됩니다.

1. 입력 처리:
   • 주문받은 그릇 수 N과 웍의 개수 M 입력
   • 웍의 용량 리스트 S 입력
2. 후보 목록 구성:
   • 단일 웍 사용 후보 추가
   • 두 웍 동시 사용 후보 추가 (중복 없이, N 이하인 값만)
3. DP 초기화:
   • dp 배열의 크기를 N+1로 만들고, dp[0] = 0으로 초기화
4. DP 전이:
   • 0부터 N까지 각 상태에 대해, 각 후보를 더해 dp 테이블 갱신
5. 최종 결과 출력:
   • dp[N] 출력 (만약 dp[N]이 -1이면, N그릇을 만드는 것이 불가능한 경우)

---

5. 예시를 통한 설명

예를 들어,

• 입력: N = 5, M = 2, 웍 용량 S = [1, 3]
• 후보 목록:
  • 단일: 1, 3
  • 두 웍 동시: 1+3 = 4
  • 최종 후보: {1, 3, 4}

DP 전이 과정:

• 초기: dp[0] = 0, dp[1..5] = -1
• i = 0에서:
  • 0 + 1 = 1 → dp[1] = 1
  • 0 + 3 = 3 → dp[3] = 1
  • 0 + 4 = 4 → dp[4] = 1
• i = 1에서 (dp[1] = 1):
  • 1 + 1 = 2 → dp[2] = 2
  • 1 + 3 = 4 → dp[4] 이미 1이므로 갱신할 필요 없음
  • 1 + 4 = 5 → dp[5] = 2
• 이후 i = 2,3,... 진행하면 최종적으로 dp[5] = 2임을 확인할 수 있습니다.

즉, 2번의 요리로 5그릇을 만들 수 있음을 알 수 있습니다.

---

요약

1. 후보 목록 구성:
   • 단일 웍 사용 (각 웍의 용량)
   • 두 웍 동시 사용 (서로 다른 두 웍의 용량 합)
2. DP 접근:
   • dp[0] = 0에서 시작하여, 각 상태에서 후보 값을 더해 최종적으로 dp[N] (N그릇을 만드는 최소 요리 횟수)을 구함
3. 예시를 통한 검증:
   • N=5, 웍이 [1, 3]인 경우, 2번의 요리로 5그릇을 만들 수 있음

 

GPT의 힘을 빌려서 작성하였다. DP는 잘 이해가 되지 않는다. DP에 대해서 다시 공부해야겠다.