문제:
풀이:
각 소형 기관차가 끌 수 있는 객차 수를 3칸이라고 하자.
객차의 수는 12개로 각 객차에 타있는 손님 수는 35, 40, 50, 10, 30, 45, 60, 20, 10, 50, 40, 70 이다.
그렇다면 아래와 같은 전제를 도출할 수 있을 것이다.
- 각 소형 기관차가 끌 수 있는 최대 인원은 연속되는 객차 3개의 인원의 합이다.
고로 1~3번째 객차, 2~4번째 객차....10~12번째 객차만 고려하면 된다. - 두 소형 기관차가 끌 수 있는 최대 인원은 객차 6개의 인원의 합이다.
고로 1~6번째 객차, 2~7번째 객차....7~12번째 객차만 고려하면 된다. - 모든 소형 기관차가 끌 수 있는 최대 인원은 객차 9개의 합이다.
고로 1~9번째 객차, 2~10번째 객차....4~12번째 객차만 고려하면 된다.
위와 같은 전제를 통해 아래와 같은 표가 나올 것이다.
| 35명 | 40명 | 50명 | 10명 | 30명 | 45명 | 60명 | 20명 | 10명 | 50명 | 40명 | 70명 |
| 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 | 8번 | 9번 | 10번 | 11번 | 12번 |
| 0 | 0 | 125 | |||||||||
| 0 | 0 | 0 | 0 | 0 | 210 | 210 | |||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 300 |
맨 밑이 3번 경우, 즉 모든 소형 기관차에 탈 수 있는 인원의 합이다. 8번째까지는 고려하지 않아도 된다.
9개의 객차를 나를 수 있는데, 굳이 8개의 객차만 나를 이유가 없기 때문이다.
그렇다면 10번 객차까지 포함했을 때, 모든 소형 기관차에 탈 수 있는 인원의 최댓값은 얼마일까?
바로 10번 객차를 포함했을 때, 최대 인원과 10번 객차를 포함하지 않았을 때 최대 인원을 비교하면 된다!!
- 10번 객차를 포함하지 않았을 때 최대 인원은 이미 구했다. 300명이다.
- 10번 객차를 포함할 때는, 무조건 8,9,10번 객차가 포함되어야 한다. 연속된 객차만 끌 수 있기 때문이다.
즉, 7번 객차까지 두 소형 기관차가 끌 수 있는 최대 인원을 알아내고, 8, 9, 10번 객차의 인원과 합한 값과,
300명을 비교하면 될 것이다.
그렇다면 7번 객차까지 두 소형 기관차가 끌 수 있는 최대 인원은 어떻게 알아낼까? 위와 매우 유사한 방법을 이용한다.
- 6번 객차를 포함하지 않았을 때 두 소형 기관차가 끌 수 있는 최대 인원은 이미 구했다. 210명이다.
- 7번 객차를 포함할 때는, 무조건 5, 6, 7번 객차가 포함되어야 한다.
즉, 4번 객차까지 하나의 소형 기관차가 끌 수 있는 최대 인원을 알아내고, 5, 6, 7번 객차의 인원과 합한 값과,
210명을 비교하면 될 것이다.
결국 2,3,4번 객차의 인원 합과 1,2,3번 객차의 인원 합을 비교하면 된다.
이것을 점화식으로 나타내면 MAX[3] vs SUM[4] - SUM[1] 이다.
위 풀이과정을 토대로 10번 객차까지 포함했을 때, 모든 소형 기관차에 탈 수 있는 인원을 구해보자.
| 35명 | 40명 | 50명 | 10명 | 30명 | 45명 | 60명 | 20명 | 10명 | 50명 | 40명 | 70명 |
| 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 | 8번 | 9번 | 10번 | 11번 | 12번 |
| 0 | 0 | 125 | 125 vs 100 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 210 | 210 vs 260 | |||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 300 | 300 vs 340 |
10번 객차까지 포함했을 때, 모든 소형 기관차에 탈 수 있는 최대 인원은 340명 이라는 것을 알 수 있다.
위와 같은 방법을 통해 풀이를 끝까지 진행하면,
소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 알 수 있을 것이다.
점화식 MAX[3] vs SUM[4] - SUM[1]을 쉽게 표현하기 위해 SUM 배열이 필요할 것이다.
위 풀이를 코드로 나타내기 위해 아래와 같이 전역변수를 설정해준다.
static int N;
static int[] cars;
static int M;
static int[] sum;
static int[][] dp;아래와 같이 입력을 받아준다.
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
cars = new int[N+1];
sum = new int[N+1];
for (int i = 1; i <= N; i++) {
cars[i] = sc.nextInt();
sum[i] = sum[i-1] + cars[i];
}
M = sc.nextInt();
dp = new int[4][N+1];dp 배열에 위에서 설명한 소형 기관차 수에 따른 최댓값을 저장할 것이다.
이제 아래 표에서 문제를 풀어나가는 방식을 그대로 코드로 작성해보자
| 35명 | 40명 | 50명 | 10명 | 30명 | 45명 | 60명 | 20명 | 10명 | 50명 | 40명 | 70명 |
| 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 | 8번 | 9번 | 10번 | 11번 | 12번 |
| 0 | 0 | 125 | 125 vs 100 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 210 | 210 vs 260 | |||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 300 | 300 vs 340 |
for (int i = M; i <= N; i++) {
if (i >= M) { // 기관차 1개
dp[1][i] = Math.max(dp[1][i-1], sum[i] - sum[i-M]);
}
if (i >= M*2) { // 기관차 2개
dp[2][i] = Math.max(dp[2][i-1], dp[1][i-M] + sum[i] - sum[i-M]);
}
if (i >= M*3) { // 기관차 3개
dp[3][i] = Math.max(dp[3][i-1], dp[2][i-M] + sum[i] - sum[i-M]);
}
}
System.out.println(dp[3][N]);- 기관차 하나일 때 객차 번호에 따른 최대 인원을 구하기 위해서는
이전 객차까지의 최대 인원 vs 지금 객차를 포함한 최대인원 의 결과를 적용시켜준다.
코드로 나타내면 dp[1][i] = Math.max(dp[1][i-1], sum[i] - sum[i-M]); 이다. - 기관차 두개일 때 객차 번호에 따른 최대 인원을 구하기 위해서도
이전 객차까지의 최대 인원 vs 지금 객차를 포함한 최대인원의 결과를 적용시켜준다.
지금 객차를 포함한 최대인원은 1번 과정에서 생성된 배열을 이용한다. 표와 함께 코드를 보면 이해가 빠를 것이다.
dp[2][i] = Math.max(dp[2][i-1], dp[1][i-M] + sum[i] - sum[i-M]); - 3번 과정은 2번 과정과 거의 다를게 없다.
dp[3][i] = Math.max(dp[3][i-1], dp[2][i-M] + sum[i] - sum[i-M]); - dp[3][N]을 출력해준다. 배열의 마지막에 저장되어 있는 값이 최댓값이다.
위의 코드를 보면 뭔가 더 간단하게 코드를 작성할 수 있을 것 같다. 아래 표를 보자.
| 35명 | 40명 | 50명 | 10명 | 30명 | 45명 | 60명 | 20명 | 10명 | 50명 | 40명 | 70명 |
| 1번 | 2번 | 3번 | 4번 | 5번 | 6번 | 7번 | 8번 | 9번 | 10번 | 11번 | 12번 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 125 | 125 vs 100 | ||||||||
| 0 | 0 | 0 | 0 | 0 | 210 | 210 vs 260 | |||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 300 | 300 vs 340 |
위의 표와 같이 원래 표 상단에 0으로 채워진 행을 추가하면 코드를 아래와 같이 작성할 수 있다.
for (int i = M; i <= N; i++) {
if (i >= M) {
dp[1][i] = Math.max(dp[1][i-1], dp[0][i-M] + sum[i] - sum[i-M]);
}
if (i >= M*2) {
dp[2][i] = Math.max(dp[2][i-1], dp[1][i-M] + sum[i] - sum[i-M]);
}
if (i >= M*3) {
dp[3][i] = Math.max(dp[3][i-1], dp[2][i-M] + sum[i] - sum[i-M]);
}
}if 문 내부의 형식이 통일되게 되었고 아래와 같은 코드로 변환하여 같은 역할을 하는, 더 짧은 코드를 작성할 수 있다.
for (int i = 1; i < 4; i++) {
for (int j = i * M; j <= N; j++) {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-M] + sum[j] - sum[j-M]);
}
}
System.out.println(dp[3][N]);
전체코드:
import java.util.*;
public class 소형기관차_2616번 {
static int N;
static int[] cars;
static int M;
static int[] sum;
static int[][] dp;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
cars = new int[N+1];
sum = new int[N+1];
for (int i = 1; i <= N; i++) {
cars[i] = sc.nextInt();
sum[i] = sum[i-1] + cars[i];
}
M = sc.nextInt();
dp = new int[4][N+1];
for (int i = 1; i < 4; i++) {
for (int j = i * M; j <= N; j++) {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j-M] + sum[j] - sum[j-M]);
}
}
System.out.println(dp[3][N]);
}
}
시행착오:
처음에는 방식이 잘 떠오르지 않았다. 결국 다중 for문을 사용하여 문제를 풀었고, 시간 초과가 걸리게 되었다.
import java.util.*;
public class 소형기관차_2616번_시간초과 {
static int N;
static int[] cars;
static int M;
static int[] dp;
static int max;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
cars = new int[N];
for (int i = 0; i < N; i++) {
cars[i] = sc.nextInt();
}
M = sc.nextInt();
dp = new int[N-M+1];
for (int i = 0; i <= N-M; i++) {
dp[i] = addCars(i);
}
findMax();
System.out.println(max);
}
static void findMax() {
for (int i = 0; i <= N-M*3; i++) {
for (int j = i+M; j <= N-M*2; j++) {
for (int k = j+M; k <= N-M; k++) {
max = Math.max(max, dp[i] + dp[j] + dp[k]);
}
}
}
}
static int addCars(int start) {
int sum = 0;
for (int i = start; i < start + M; i++) {
sum += cars[i];
}
return sum;
}
}
addCars()메서드에 빠져 허우적거리다, 결국 다른 블로그를 참고했다.
[BOJ] 2616 소형기관차 - JAVA (tistory.com)
[BOJ] 2616 소형기관차 - JAVA
1. 문제 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입
january-diary.tistory.com
설명이 정말 잘 되어있었고, 그려진 표를 보니 코드를 보지 않고도 이해가 되었다.
아직 dp를 잘 못하는것 같아 더 연습 해야겠다는 생각이 들었다.
또한 위의 블로그를 보고, 시각 자료에 대한 중요성을 더 크게 느끼게 되었다. 앞으로는 더 효과적인 시각자료를 이용해봐야겠다.
'알고리즘 > 백준' 카테고리의 다른 글
| 12869번 - 뮤탈리스크(bfs) (0) | 2024.08.27 |
|---|---|
| 10422번- 괄호(dp, 카탈랑 수) (0) | 2024.08.21 |
| 2281번 - 데스노트(dp) (0) | 2024.08.16 |
| 5557번 - 1학년(dp) (0) | 2024.08.15 |
| 12865번 - 평범한배낭(dp) (0) | 2024.08.15 |
