두 배낭 문제

두 개의 배낭 문제

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1초	1024 MB	2029	489	489	55.280%

문제

승형이와 원빈이는 배낭여행을 가기 위해 두 개의 배낭을 준비했다. 각 배낭에는 $N$개의 물건이 들어있으며:

• 첫 번째 배낭에는 $A_1, A_2, \dots, A_N$의 무게를 가진 물건들이 아래에서 위로 순서대로 쌓여 있다. $A_N$이 맨 위에 있는 물건의 무게이다.
• 두 번째 배낭에는 $B_1, B_2, \dots, B_N$의 무게를 가진 물건들이 아래에서 위로 순서대로 쌓여 있다. $B_N$이 맨 위에 있는 물건의 무게이다.

배낭의 무게는 배낭 안에 남아있는 물건들의 무게의 합으로 정의된다. 원빈이는 최대 $K$번 두 배낭 중 하나를 선택하여 맨 위에 있는 물건을 없앨 수 있다.

입력

첫 번째 줄에 두 정수 $N$과 $K$가 주어진다. $(1 \leq N \leq 10^5, 0 \leq K \leq 2N)$
두 번째 줄에 첫 번째 배낭의 물건들의 무게를 나타내는 $N$개의 정수 $A_1, A_2, \dots, A_N$이 주어진다. $(1 \leq A_i \leq 10^9)$
세 번째 줄에 두 번째 배낭의 물건들의 무게를 나타내는 $N$개의 정수 $B_1, B_2, \dots, B_N$이 주어진다. $(1 \leq B_i \leq 10^9)$

출력

원빈이가 들어야 하는 배낭의 무게의 최솟값을 출력한다.

예제 입력/출력

입력 1

3 2
3 1 4
1 5 9

출력 1

6

설명: 원빈이는 첫 번째 배낭에서 맨 위의 물건을 없애고, 두 번째 배낭에서 맨 위의 물건을 없앨 수 있다. 최종적으로 남아있는 배낭의 무게는 4와 6이고, 원빈이는 무게 6의 배낭을 메게 된다.

입력 2

3 0
3 1 4
1 5 9

출력 2

15

노트

이 문제는 입력 데이터의 용량이 커서, 시간 초과를 받지 않으려면 빠른 입출력 방법을 사용해야 할 수 있다.

• C++을 사용하고 있고 cin/cout을 사용하고자 한다면:
  • cin.tie(nullptr)와 ios::sync_with_stdio(false)를 main 함수 안의 맨 위에 적는다.
  • endl 대신 개행 문자(\n)를 사용한다.
  • 단, 이렇게 할 경우 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.
• Java를 사용하고 있다면:
  • Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용한다.
  • BufferedWriter.flush를 마지막에 한 번 수행한다.
• Python을 사용하고 있다면:
  • input 대신 sys.stdin.readline을 사용한다. 단, 이 함수는 맨 끝의 개행 문자까지 같이 입력받음에 유의한다.
  • 개행 문자를 제외한 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다.

 

1. 문제 요약

• 두 개의 배낭 A와 B가 있으며, 각 배낭에는 아래에서 위로 순서대로 (N)개의 물건이 쌓여 있습니다.
• 각 배낭의 무게는 남아있는 물건들의 무게의 합입니다.
• 원빈이는 최대 (K)번 두 배낭 중 하나를 선택하여 맨 위의 물건을 제거할 수 있습니다.
• 승형이는 원빈이의 행동 후 항상 두 배낭 중 더 가벼운 배낭을 선택합니다.
• 원빈이는 승형이가 선택하지 않은 배낭을 메야 합니다.
• 목표는 원빈이가 메야 하는 배낭의 무게의 최솟값을 구하는 것입니다.

2. 입력 처리

import os
N, K, *r = map(int, os.read(0, os.fstat(0).st_size).split())
A, B = r[:N], r[N:]

• 표준 입력에서 데이터를 읽어 변수에 저장합니다.
  • N: 각 배낭의 물건 수 ((1 \leq N \leq 10^5))
  • K: 원빈이가 제거할 수 있는 최대 물건 수 ((0 \leq K \leq 2N))
  • A: 배낭 A의 물건 무게 리스트
  • B: 배낭 B의 물건 무게 리스트

3. 전체 무게 계산

total_A, total_B = sum(A), sum(B)
NP = N + 1

• total_A: 배낭 A의 전체 무게
• total_B: 배낭 B의 전체 무게
• NP: 반복문에서 사용하기 위해 (N + 1)로 설정

4. 맨 위에서부터의 누적 합 계산

cum_A = [0] * NP
cum_B = [0] * NP
for i in range(1, NP):
    cum_A[i] = cum_A[i - 1] + A[N - i]
    cum_B[i] = cum_B[i - 1] + B[N - i]

• cum_A[i]: 배낭 A에서 맨 위부터 (i)개의 물건의 무게 합
• cum_B[i]: 배낭 B에서 맨 위부터 (i)개의 물건의 무게 합
• A[N - i]와 같이 인덱스를 사용하여 맨 위에서부터 순서대로 접근

예제 입력 1 적용

N = 3, K = 2
A = [3, 1, 4]
B = [1, 5, 9]

배낭 A의 누적 합 cum_A 계산:

i	cum_A[i] 계산	cum_A[i]
1	cum_A[0] + A[2] = 0+4	4
2	cum_A[1] + A[1] = 4+1	5
3	cum_A[2] + A[0] = 5+3	8

결과: cum_A = [0, 4, 5, 8]

배낭 B의 누적 합 cum_B 계산:

i	cum_B[i] 계산	cum_B[i]
1	cum_B[0] + B[2] = 0+9	9
2	cum_B[1] + B[1] = 9+5	14
3	cum_B[2] + B[0] = 14+1	15

결과: cum_B = [0, 9, 14, 15]

5. 각 경우의 남은 배낭 무게 계산

W_A = [total_A - cum_A[t] for t in range(NP)]
W_B = [total_B - cum_B[s] for s in range(NP)]

• W_A[t]: 배낭 A에서 맨 위부터 (t)개의 물건을 제거했을 때 남은 무게
• W_B[s]: 배낭 B에서 맨 위부터 (s)개의 물건을 제거했을 때 남은 무게

예제 입력 1 적용

배낭 A의 남은 무게 W_A:

t	W_A[t] 계산	W_A[t]
0	8 - 0	8
1	8 - 4	4
2	8 - 5	3
3	8 - 8	0

배낭 B의 남은 무게 W_B:

s	W_B[s] 계산	W_B[s]
0	15 - 0	15
1	15 - 9	6
2	15 - 14	1
3	15 - 15	0

6. 최소 무게 계산

min_weight = float('inf')
max_t = min(N, K)
for t in range(0, max_t + 1):
    s = min(K - t, N)
    weight = max(W_A[t], W_B[s])
    if weight < min_weight:
        min_weight = weight

• t: 배낭 A에서 제거할 물건의 수 ((0 \leq t \leq \min(N, K)))
• s: 배낭 B에서 제거할 물건의 수 ((s = K - t), 단 (0 \leq s \leq N))
• 각 경우마다 두 배낭의 남은 무게 중 큰 값을 선택 (원빈이가 메야 하는 배낭)
• 그 중 최소값을 min_weight에 저장

예제 입력 1 적용

가능한 (t)와 (s)의 조합:

• (t = 0)
  • (s = \min(2 - 0, 3) = 2)
  • 남은 무게: (W_A[0] = 8), (W_B[2] = 1)
  • 원빈이가 메야 하는 배낭의 무게: (\max(8, 1) = 8)
  • 현재 최소 무게: (8)
• (t = 1)
  • (s = \min(2 - 1, 3) = 1)
  • 남은 무게: (W_A[1] = 4), (W_B[1] = 6)
  • 원빈이가 메야 하는 배낭의 무게: (\max(4, 6) = 6)
  • 현재 최소 무게: (6)
• (t = 2)
  • (s = \min(2 - 2, 3) = 0)
  • 남은 무게: (W_A[2] = 3), (W_B[0] = 15)
  • 원빈이가 메야 하는 배낭의 무게: (\max(3, 15) = 15)
  • 현재 최소 무게: (6) (변동 없음)

따라서 원빈이가 메야 하는 배낭의 최소 무게는 (6)입니다.

7. 결과 출력

print(min_weight)

• 계산된 최소 무게를 출력합니다.

8. 시간 복잡도 계산

• 입력 데이터의 크기: (N \leq 10^5), (K \leq 2N)
• 누적 합 계산:
  • 반복문은 (i = 1)부터 (N)까지 실행되므로, 시간 복잡도는 (O(N))
• 최소 무게 계산:
  • 반복문은 (t = 0)부터 (\min(N, K))까지 실행
  • (K \leq 2N)이므로 최대 반복 횟수는 (N)에 비례
  • 시간 복잡도는 (O(N))
• 전체 시간 복잡도:
  • (O(N) + O(N) = O(N))
• 이는 문제의 시간 제한 내에서 수행 가능합니다.

9. 공간 복잡도 계산

• 추가로 사용하는 배열:
  • cum_A, cum_B: 크기 (N + 1)
  • W_A, W_B: 크기 (N + 1)
• 공간 복잡도는 (O(N))

10. 결론

• 문제의 조건을 활용하여 누적 합을 계산하고, 가능한 모든 경우의 조합을 고려하여 원빈이가 메야 하는 배낭의 최소 무게를 구했습니다.
• 시간 복잡도와 공간 복잡도 모두 (O(N))으로, 주어진 제약 조건 내에서 해결할 수 있습니다.

 

def sol():
    import os
    N,K,*r=map(int,os.read(0,os.fstat(0).st_size).split())
    A,B=r[:N],r[N:]
    total_A, total_B = sum(A), sum(B)
    NP=N+1
    cum_A = [0]*NP
    cum_B = cum_A[:]
    for i in range(1,NP):
        cum_A[i] = cum_A[i - 1] + A[N - i]
        cum_B[i] = cum_B[i - 1] + B[N - i]
    W_A = [total_A - cum_A[t] for t in range(NP)]
    W_B = [total_B - cum_B[s] for s in range(NP)]
    min_weight = float('inf')
    max_t = min(N, K)
    for t in range(0, max_t + 1):
        s = min(K - t, N)
        weight = max(W_A[t], W_B[s])
        if weight < min_weight:
            min_weight = weight
    print(min_weight)
sol()