문제 설명
1 년치 수영장 이용 계획이 주어졌을 때, 1일, 1달, 3달, 1년 이용권 네 가지를 잘 조합하여 최소 요금을 찾는 문제
전체 코드 흐름
dp 로 최소 비용을 계산하기 !
먼저, 예시를 통해 이해하기 위해 아래 가격표와 월별 이용 횟수를 참고해봅시다.
| 1일권 | 1개월권 | 3개월권 | 12개월권 |
|---|---|---|---|
| 10원 | 100 원 | 50 원 | 300 원 |
<가격표>
| 1월 | 2월 | 3월 | 4월 | 5월 | 6월 | 7월 | 8월 | 9월 | 10 월 | 11월 | 12월 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 6 | 2 | 7 | 8 |
<월별 이용횟수>
그렇다면 아래 표와 같이 월별 누적 최솟값을 구할 것입니다.
| 1월 | 2월 | 3월 | 4월 | 5월 | 6월 | 7월 | 8월 | 9월 | 10 월 | 11월 | 12월 | 13월 | 14월 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 60 | 80 | 50 | 110 | 110 | 100 |
어떻게 이 표와 같이 나왔을까요?
그리고 13월과 14월은 무슨 이야기일까요?
핵심 아이디어
저는 이 문제에서 연산될 수 있는 경우의 수를 세 가지로 나누었습니다.
1️⃣ 1일 이용권 vs 1달 이용권 비교(1번)
- 해당 월의 이용 일수 * 1일 이용권 가격과 한 달 이용권의 가격을 비교하여 둘 중 최솟값 A를 구합니다.
-> 이번 달까지의 최소 비용 = "A + 이전 달 까지의 최소 누적 이용료" 로 갱신합니다.
9월:
min(60, 100)= 60
10월:min(60 + 20, 60 + 100)= 80
2️⃣ vs 3달 이용권(2번)
- 3월 부터는, 세 달 이용권을 적용할 수 있습니다.
-> 이번 달까지의 최소 비용 = 1번에서 구한 이번 달까지의 최소 비용과 3달 전까지의 최소 이용 요금 + 3개월 이용권 중 최솟값으로 갱신합니다.
11월
1번 적용:min(80 + 70, 80 + 80 + 100)= 150
2번 적용:min(150, 0 + 50)= 50
최종 11월 누적 최솟값: 50
3️⃣ vs 1년 이용권(3번)
- 12월에는, 1년 이용권을 적용할 수 있습니다.
-> 이번 달까지의 최소 비용 = 2번에서 구한 이번 달 최소 비용과 1년 이용권 금액을 비교하여 최솟값으로 갱신합니다.
12월
1번 적용:min(50 + 80, 50 + 100)= 130
2번 적용:min(130, 60 + 50)= 110
3번 적용:min(110, 300)= 110
따라서, 이 흐름대로라면 최종 12월까지의 최솟값은 110원입니다.
즉 1번 까지만 연산하는 경우, 2번까지 연산하는 경우, 3번까지 연산하는 경우로 나눌 수 있겠습니다.
각 월 별 해당하는 경우를 표로 정리하면 다음과 같습니다.
| 월 | 고려 가능한 경우의 수 |
|---|---|
| 1월, 2월 | ① 하루 요금 vs 1달 요금 |
| 3월 ~ 11월 | ① 하루 요금 vs 1달 요금 ② vs 3달 요금 |
| 12월 | ① 하루 요금 vs 1달 요금 ② vs 3달 요금 ③ vs 1년 요금 |
이걸 코드로 짜면 됩니다 !! 👏
그러면 ! 13월과 14월은 뭔가요 ?
처음에는 3달 이용권을 11월에도, 12월에도 쓸 수 있다는 조건을 생각 못했습니다.
11월 12월에도 3개월권을 썼을 때의 결과를 알기 위해 단순히 dp 결과값을 저장하는 배열을 두 개 더 늘려줘서 12월이 아닌 14월까지 반복문을 돌게 해줬습니다.
| 월 | 고려 가능한 경우의 수 |
|---|---|
| 13월, 14월 | ② 3달 요금 vs 앞의 최소값 |
따라서, 코드에 이 요소를 추가해 줍니다 !
13월
min(110, 80 + 50) = 110
14월
min(110, 50 + 50) = 100
이로써 최종 누적 요금 최솟값은 100원이 됩니다 !
+ 나름의 최적화..!?
10 100 50 300
0 0 0 0 0 0 0 0 6 2 7 8
위와 같은 input 이 들어왔을 때 0번째 인덱스부터 0이 연속으로 나온 부분은 건너뛰고, 첫 숫자가 나오는 부분인 6부터 계산을 수행해줬습니다.
그리고 처음 0이 아닌 숫자가 나온 곳을 1월이라 간주하고 계산을 수행해주었습니다.
전체 코드
C++ 코드
#include <iostream>
#include <cstring>
using namespace std;
int oneDay, oneMonth, threeMonth, oneYear;
int plan[15], result[15];
void init() {
memset(plan, 0, sizeof(plan));
memset(result, 0, sizeof(result));
}
void dp() {
int tmp1, tmp2, tmp3, i = 1, cnt = 0;
while (plan[i] == 0) i++;
for (; i <= 14; i++) {
int prev = result[i - 1];
if (i == 13 || i == 14) result[i] = result[i - 1];
else {
tmp1 = plan[i] * oneDay + prev;
tmp2 = (plan[i] != 0) ? oneMonth + prev : prev;
result[i] = min(tmp2, tmp1);
}
if (cnt < 2) {
cnt++;
continue;
}
else {
result[i] = min(result[i], result[i - 3] + threeMonth);
if (i == 12) result[i] = min(result[i], oneYear);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++) {
init();
cin >> oneDay >> oneMonth >> threeMonth >> oneYear;
for (int i = 1; i <= 12; i++) {
cin >> plan[i];
}
dp();
cout << "#" << tc << " " << result[14] << "\n";
}
}java 코드
import java.io.*;
import java.util.*;
public class Solution {
static int oneDay, oneMonth, threeMonth, oneYear;
static int []plan = new int[15];
static int []result = new int[15];
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
for (int tc = 1; tc <= t; tc++) {
Arrays.fill(plan, 0);
Arrays.fill(result, 0);
StringTokenizer st = new StringTokenizer(br.readLine());
oneDay = Integer.parseInt(st.nextToken());
oneMonth = Integer.parseInt(st.nextToken());
threeMonth = Integer.parseInt(st.nextToken());
oneYear = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= 12; i++) {
plan[i] = Integer.parseInt(st.nextToken());
}
dp();
sb.append("#").append(tc).append(" ").append(result[14]).append("\n");
}
System.out.print(sb);
}
public static void dp() {
int i = 1, tmp1, tmp2, cnt = 0;
while (plan[i] == 0) i++;
for (; i < 15; i++) {
if (i != 13 && i != 14) {
tmp1 = result[i - 1] + plan[i] * oneDay;
tmp2 = (plan[i] == 0) ? result[i - 1] : result[i - 1] + oneMonth;
result[i] = Math.min(tmp1, tmp2);
} else result[i] = result[i - 1];
if (cnt < 2) {
cnt++;
continue;
}
result[i] = Math.min(result[i], result[i - 3] + threeMonth);
if (i == 12) result[i] = Math.min(result[i], oneYear);
}
}
}실행 결과
