[백준] 2616 소형기관차

📖 문제

---

🧑🏻‍💻 풀이 과정

1) 문제 접근 및 이해

연속된 특정 구간의 합을 이용하여 최대의 값을 구하여야 했으므로 누적합을 이용하였습니다.

누적합을 이용하여 객차의 구간별로 이송 가능한 인원 수를 빠르게 구할 수 있도록 하였습니다.

 

소형 기관차가 객차를 선택하는 경우에 따라 최대 인원을 구할 수 있었으므로 완전탐색을 이용하여 최대 이송이 가능한 경우를 탐색하였습니다.

그러나 객차의 수가 많아질수록 경우의 수가 다양해지기 때문에 시간 초과 문제가 발생하였습니다.

 

시간을 줄이기 위하여 DP를 이용하여 최대 이송 인원을 구하였습니다.

2차원 배열을 이용하여 행에는 소형 기관차를 사용하는 개수로 기록하였고, 열에는 객차의 번호로 사용하여 소형 기관차의 사용 개수와 끌고 가는 객차의 번호에 따라 인원수가 기록되도록 하였습니다.

2) 알고리즘

• 누적합
• DP

3) 풀이 코드

사용 언어 - Python

import sys
sys.stdin = open('input.txt')

N = int(sys.stdin.readline())                               # 객차의 개수
carriage = list(map(int, sys.stdin.readline().split()))     # 객차별 사람 수
can_carriage = int(sys.stdin.readline())                    # 소형 기관차가 끌 수 있는 최대 객차 수

acc_people = [0]                                # 사람 수 누적합
dp = [[0] * (N+1) for _ in range(4)]            # 객차 선택에 따른 최대 사람 수 DP

for i in range(1, N+1):                         # 첫 객차부터 누적합 구하기
    acc = acc_people[-1] + carriage[i-1]
    acc_people.append(acc)

for i in range(1, 4):                           # 소형 기관차 사용하는 개수 (총 3개)
    for j in range(i * can_carriage, N+1):      # 끌고 가는 객차 시작 번호
        people = acc_people[j] - acc_people[j-can_carriage]             # 현재 객차를 시작으로 끌었을 때 최대 인원수
        dp[i][j] = max(dp[i][j-1], dp[i-1][j-can_carriage] + people)    # 이전 경우 / 소형 기관차 하나 덜 썼을때 최대 인원 수와 기관차 하나 더 써서 추가된 인원수 합
                                                                        # 둘 중에 더 큰 값 기록
print(dp[-1][-1])           # 기관차 3개를 사용하고, 최대로 이송 가능한 인원 수 출력

---

🔗 문제 링크

- https://www.acmicpc.net/problem/2616

2616번: 소형기관차

 

 

※ 오류 및 오타, 다른 의견이 있는 경우 댓글을 남겨주시면 감사하겠습니다