[백준/DP] 2616 소형기관차 - 자바

2024. 2. 3. 14:43· Problem Solving/CT-Java
목차
  1. 문제
  2. 풀이

(obsidian 기록일 : 24년 1월 1일)

문제

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

 

2616번: 소형기관차

첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있

www.acmicpc.net


풀이

변수선언

  • int[i] trainGuest : 기차탄 손님
  • int[i] guestSum : 기차탄 손님 누적합
  • int[i][j] dp : 소형기관차 i개로 j칸을 끌고갈 때 최대로 운송할 수 있는 손님의 수
  • M : 한개의 소형 기관차가 끌 수 있는 최대 객차의 수

 

예시 입력값

N = 7, M = 2

손님수 35 40 50 10 30 45 60
누적합 35 75 125 135 165 210 270

 

객차에 승객 수는 두 조건으로 나눌 수 있다.

1. dp[i][j - 1] >= j 번째 객차를 선택하지 않을시 이전객차의 최대 승객수

2. dp[i - 1][j - m] + (guestSum[j] - guestSum[j - m]) : j번째 객차 선택...

즉, i-1개 소형기관차 선택시에 첫번째 객차부터 j-m 까지 인원채대 승객 합 + j - m 부터 j 까지의 승객합을 나타냄.

 

점화식은 그러므로 다음과 같다 dp[i][j] = Math.max(1번 조건, 2번 조건)

 

import java.io.*;
import java.util.*;

public class BOJ_2616_G3_소형기관차 {
    static int n, m;
    public static void main(String[] args) throws Exception {
        // start :: input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        int[] trainGuest = new int[n + 1];
        int[] guestSum = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            trainGuest[i] = Integer.parseInt(st.nextToken());
            guestSum[i] = trainGuest[i] + guestSum[i - 1];
        }
        m = Integer.parseInt(br.readLine());
        int[][] dp = new int[4][n+1];
        int ans = 0;
        // end :: input

        for (int i = 1; i <= 3; i++) {
            for (int j = i * m; j <= n; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j - m] + (guestSum[j] - guestSum[j - m]) );
            }
        }

        System.out.println(dp[3][n]);
    }

}

'Problem Solving > CT-Java' 카테고리의 다른 글

[백준/DP-DFS] 1103 게임 - 자바  (0) 2024.02.03
[백준/그리디] 2457 공주님의 정원 - 자바  (0) 2024.02.03
[프로그래머스/문자열] 17677 [1차] 뉴스 클러스터링 - JAVA  (0) 2023.09.18
[프로그래머스/구현] 77485 행렬 테투리 회전하기 - JAVA  (0) 2023.09.16
[프로그래머스/문자열] 60065 튜플 - JAVA  (0) 2023.09.16
  1. 문제
  2. 풀이
'Problem Solving/CT-Java' 카테고리의 다른 글
  • [백준/DP-DFS] 1103 게임 - 자바
  • [백준/그리디] 2457 공주님의 정원 - 자바
  • [프로그래머스/문자열] 17677 [1차] 뉴스 클러스터링 - JAVA
  • [프로그래머스/구현] 77485 행렬 테투리 회전하기 - JAVA
White Han
White Han
Software Developer
White Han
sudo apt-get happiness
White Han
전체
오늘
어제
  • 분류 전체보기 (183)
    • Language (35)
      • Java (17)
      • Java-Weekly-study (0)
      • Python (18)
    • BackEnd (11)
      • Server (2)
      • Spring (3)
      • Spring Security (0)
      • JDBC (1)
      • NodeJS (2)
      • LINUX (3)
    • DataBase (10)
      • MySQL (5)
      • MongoDB (4)
      • Oracle (1)
    • Infra (4)
      • Docker (4)
    • CS (38)
      • OS (38)
    • Problem Solving (79)
      • Algorithm (8)
      • CT-Java (30)
      • CT-Python (41)
    • IDE (1)
      • eclipse (1)
      • vscode (0)
    • Etc. (3)
      • Git (1)
      • TDD, Refactor, CleanCode (1)
      • Conference (1)
    • 기록 (2)
      • 후기 (1)
      • 프로젝트 회고록 (1)

블로그 메뉴

  • 홈
  • 태그
  • 방명록
  • 글쓰기

공지사항

  • 방문해 주셔서 감사합니다.

인기 글

태그

  • javascript identifier
  • 자바스크립스 식별자 종류
  • javascript
  • 사무용 모니터
  • 자바스크립트
  • 자바스크립트 식별자
  • 자바스크립트 개념
  • 자바 super
  • 알파스캔 모니터
  • 자바 inheritance
  • 싸피 후기
  • 운영체제 구조
  • 사무용 모니터 추천
  • 자바 this
  • Java super
  • Java this
  • OS
  • java
  • 프로세서
  • 24인치 모니터 추천
  • 알파스캔 AOC 24B1X
  • 싸피
  • AOC 24B1X
  • Java Inheritance
  • 운영체제
  • 싸피 합격
  • SSAFY
  • 운영체제 역할
  • 프로세스
  • 싸피8기

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.1
White Han
[백준/DP] 2616 소형기관차 - 자바
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.