이 영역을 누르면 첫 페이지로 이동
포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

페이지 맨 위로 올라가기

포렌식 & 개발 이야기 - Forensics & Development

Pental - Forensics / iOS / Windows / Android / Kakaotalk / Telegram / Etc

[골드 3] 백준 2616 - 소형기관차 (파이썬)

  • 2025.04.20 14:13
  • Programming/백준
글 작성자: pental

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

풀이

  • 열차는 각 객차마자 탑승 인원이 주어져있다.
  • 한번에 K개의 객차만을 끌 수 있다.
  • 최대 3번까지 소형 기관차 운행이 가능하다.
  • 최대한 많은 승객을 운송하는 것이 목표이다.

먼저 입력 및 누적합을 계산한다.

N = int(input())  # 객차 수
A = list(map(int, input().split()))  # 각 객차에 탄 승객 수
K = int(input())  # 소형 기관차가 끌 수 있는 객차 수

psum = [0] * N
psum[0] = A[0]
for i in range(1, N):
    psum[i] = psum[i - 1] + A[i]
  • psum[i]는 0부터 i번째까지의 누적합이다.
  • 구간 합 A[i - K + 1] … + A[i]는 psum[i] - psum[i - K]로 계산한다.

DP 테이블은 아래와 같이 정의한다.

D = [[0] * 4 for _ in range(N)]
  • D[i][j]는 0 ~ i 번째 까지 객차 중 j번 기관차를 사용했을때의 최대 승객 수를 의미한다.
  • j는 1 ~ 3까지 사용한다.

점화식은 아래와 같이 구성한다.

for i in range(1, 4):
    D[0][i] = A[0]  # 첫 객차만 사용할 경우 초기값 (실제론 큰 의미 없음)

for i in range(1, N):
    for j in range(1, 4):
        D[i][j] = D[i - 1][j]  # 현재 객차 포함하지 않는 경우

        if i <= K - 1:
            D[i][j] = max(D[i][j], psum[i])  # 처음부터 i까지의 합을 고를 수 있는 경우
        else:
            sum = psum[i] - psum[i - K]
            D[i][j] = max(D[i][j], sum + D[i - K][j - 1])
  • D[i][j] = max(D[i - 1][j], sum(i - K + 1 ~ i) + D[i - K][j - 1])
  • 현재 구간을 고르지 않는 경우는 D[i - 1][j]
  • 현재 구간을 고르는 경우는 이전 구간까지의 최대합 + 현재 구간 합을 지정한다.

psum은 N + 1 길이로 만들고 psum[i] = sum(A[0] ~ A[i - 1]) 식으로 하면 인덱싱이 깔끔해 질 것 같다.

코드

# 백준 2616 - 소형기관차
# 분류 - 다이나믹 프로그래밍

N = int(input())
A = list(map(int, input().split()))
K = int(input())

# sum(i - K + 1, i) = psum[i] - psum[i - K]
psum = [0] * N
psum[0] = A[0]
for i in range(1, N) :
    psum[i] = psum[i - 1] + A[i]

D = [[0] * 4 for _ in range(N)]

for i in range(1, 4) :
    D[0][i] = A[0]

for i in range(1, N) :
    for j in range(1, 4) :
        D[i][j] = D[i - 1][j]

        if i <= K - 1 :
            D[i][j] = max(D[i][j], psum[i])
        else :
            sum = psum[i] - psum[i - K]
            D[i][j] = max(D[i][j], sum + D[i - K][j - 1])

print(D[N - 1][3])
저작자표시 비영리 (새창열림)

'Programming > 백준' 카테고리의 다른 글

[골드 1] 백준 2014 - 소수의 곱 (파이썬)  (0) 2025.04.20
[실버 3] 백준 3273 - 두 수의 합 (파이썬)  (0) 2025.04.20
[골드 2] 백준 1135 - 뉴스 전하기 (파이썬)  (1) 2025.04.19
[브론즈 1] 백준 1333 - 부재중 전화 (파이썬)  (1) 2025.04.19
[실버 3] 백준 8911 - 거북이 (파이썬)  (0) 2025.04.19

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [골드 1] 백준 2014 - 소수의 곱 (파이썬)

    [골드 1] 백준 2014 - 소수의 곱 (파이썬)

    2025.04.20
  • [실버 3] 백준 3273 - 두 수의 합 (파이썬)

    [실버 3] 백준 3273 - 두 수의 합 (파이썬)

    2025.04.20
  • [골드 2] 백준 1135 - 뉴스 전하기 (파이썬)

    [골드 2] 백준 1135 - 뉴스 전하기 (파이썬)

    2025.04.19
  • [브론즈 1] 백준 1333 - 부재중 전화 (파이썬)

    [브론즈 1] 백준 1333 - 부재중 전화 (파이썬)

    2025.04.19
다른 글 더 둘러보기

정보

포렌식 & 개발 이야기 - Forensics & Development 블로그의 첫 페이지로 이동

포렌식 & 개발 이야기 - Forensics & Development

  • 포렌식 & 개발 이야기 - Forensics & Development의 첫 페이지로 이동

검색

메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

카테고리

  • Category (452)
    • Forensics (105)
      • Magnet AXIOM (28)
      • Digital Forensics Informati.. (9)
      • Iphone Forensics (24)
      • DFC (7)
      • 디지털포렌식전문가2급 자격증 (10)
      • FTK ACE 자격증 (7)
    • 이것저것 (7)
      • Ubuntu (6)
      • 디스코드 봇 (4)
      • Volatility GUI (2)
    • CTF (32)
      • NEWSECU (14)
      • CTF-d (5)
      • Puzzel - Network Forensics (2)
      • Security Traps (2)
      • system32.kr (5)
      • HMCTF (4)
    • Programming (260)
      • C (10)
      • Python (11)
      • 백준 (206)
      • 프로그래머스 (32)
    • 그냥 개발 및 잡담 (16)
      • Docker (2)
      • Google Cloud (3)
      • OS 개발 (3)
    • Best of Best (20)

최근 글

인기 글

댓글

공지사항

아카이브

태그

  • axiom
  • 포렌식
  • 디지털포렌식
  • Forensics
  • pental
  • 파이썬
  • 프로그래머스
  • 백준
  • 전체 보기…

정보

pental의 포렌식 & 개발 이야기 - Forensics & Development

포렌식 & 개발 이야기 - Forensics & Development

pental

블로그 구독하기

  • 구독하기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © pental.

티스토리툴바