[C++] 1952번 [모의 SW 역량테스트] 수영장

 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq

---

 

25/02/06

 

 

전형적인 DP문제이다. 제한이 작아서 백트래킹으로도 해결할 수 있다.

---

 

문제 접근 방식:

 

 

문제의 요구 사항은 각 달의 이용횟수가 주어지고, 하루 이용권, 한 달 이용권, 세 달 이용권, 1년 이용권의 가격이 주어질 때 수영장을 이용할 수 있는 최소 비용을 구하는 것이다.

 

나는 다음과 같이 생각했다.

 

어차피 1달, 3달, 1년 이용권은 중간에 사용할 수 없다. 정확히 말하면 중간에 사용하는 것이 손해이다.

 

예를 들어, 내가 1월에 5번 이용해야 하는데 하루는 하루 이용권을 사서 이용하고, 나머지 4일은 1달 이용권으로 이용한다면 그냥 손해다.

 

어차피 1달, 3달, 1년 이용권은 항상 연초나 매 달 1일에 시작하기 때문에 1월 중에 굳이 하루를 하루 이용권으로 이용할 필요가 없다. 그러면 더 손해를 보는 구조다.

 

즉, 이 말은 하루 이용권을 사용한다면 그 달에는 "하루 이용권 만" 사용해야한다. 다시 말하자면, 이용권은 항상 한 달 단위로 끊어진다.

 

이 상황에서 2가지 접근 방식을 소개하겠다.

 

1. 백트래킹으로 해결하는 방법

 

이용권은 한 달 단위로 끊어진다는 사실을 알고 있으므로, 다음 그림과 같은 트리 구조를 가진 백트래킹을 진행할 수 있다.

 

몇 월을 방문했는지 선언하는 Visited 배열을 선언해주면 백트래킹을 진행할 수 있을 것이다.

 

이 접근 방식의 단점은 개월 수가 많아지면 시간이 느려진다는 것이다.

 

2. DP로 해결하는 방법

 

DP테이블을 다음과 같이 정의해보자.

$$DP[i] = (i+1)\text{번째 달까지 수영장을 이용하였을 때 수영장을 이용하는 최소 비용}$$

 

편의 상 0번 인덱스를 시작으로 잡도록 테이블을 다음과 같이 정의했다.

 

그러면 DP[0], 즉, 1월 달까지 수영장을 이용하였을 때 수영장을 이용하는 최소 비용은 그 달에 하루 이용권만 사용하거나, 한달 이용권을 사용하는 경우 중 최솟값에 해당하므로, 다음과 같다.

 

$$DP[0] = \min (A[0] \times B[0], A[1])$$

 

편의 상 배열 A는 이용권의 가격을 담은 배열, 배열 B는 각 달마다의 이용 횟수를 담은 배열로 잡았다.

 

마찬가지로, DP[1], 즉, 2월 달까지 수영장을 이용하였을 때 수영장을 이용하는 최소 비용은, 이전의 (1월 달까지 이용했던 최소비용) + (2월 달에 이용하는 최소 비용)이 된다.

 

2월 달에 이용하는 최소 비용은 그 달에 하루 이용권만 사용하거나 한달 이용권을 사용하는 경우이므로, 다음과 같다.

 

$$DP[1] = DP[0]+\min(A[0] \times B[1], A[1])$$

 

DP[2], 즉, 3월 달까지 수영장을 이용하였을 때 수영장을 이용하는 최소 비용은, (1월부터 3월까지 3달 이용권을 이용하는 비용) 과 이전의 (2월 달까지 이용했던 최소 비용) + (3월 달에 이용하는 최소 비용) 중 최솟값이 되므로, 다음과 같다.

 

$$DP[2] = \min(A[2], DP[1]+\min(A[0]*B[2], A[1]))$$

 

이제, 일반화하여, $i$번째 달까지 수영장을 이용하였을때 수영장을 이용하는 최소 비용은 다음과 같다.

 

($i-3$번째 달까지 이용했을 때의 최소 비용)+(3달 이용권을 이용하는 비용) 과 ($i-1$번째 달까지 이용했을 때의 최소 비용)+($i$번째 달을 이용하는 최소 비용) 중에서의 최솟값.

 

따라서 다음과 같은 식이 나오게 된다.

 

$$DP[i] = \min(DP[i-3]+A[2], DP[i-1]+\min(A[0]*B[i], A[1]))$$

 

이후 DP[11], 즉, 12월달까지의 최소 비용을 구하려고 할 때 마지막에 연간 이용권을 사용하는 비용까지 고려해주면 된다.

 

시간 복잡도는 $\mathcal{O}(N)$으로 해결할 수 있다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// SWEA1952 수영장
// DP
/*
접근 방법:
달, 년 이용권은 어차피 중간에 사용할 수 없음.
하루 이용권을 사용한다면 그 달에는 하루 이용권만 사용해야함.
이를 통해 DP[i]를 다음과 같이 정의하자.
DP[i] = i번째 달까지 수영장을 이용하였을 때 수영장을 이용하는 최소 비용.
DP[0] = min(A[0]*B[0], A[1]);
*/
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
#define endl '\n'

void solve(int test_case_num){
    vector<int> A(4), B(12), DP(12,0);
    for (int i = 0; i < 4; i++) cin >> A[i];
    for (int i = 0; i < 12; i++) cin >> B[i];
    DP[0] = min(A[0]*B[0], A[1]);
    DP[1] = DP[0]+min(A[0]*B[1], A[1]);
    DP[2] = min(A[2], DP[1]+min(A[0]*B[2], A[1]));
    for (int i = 3; i <= 11; i++){
        DP[i] = min(DP[i-3]+A[2], DP[i-1]+min(A[0]*B[i], A[1]));
    }
    cout << '#' << test_case_num << ' ' << min(A[3], DP[11]) << endl;
    return;
}

int main(void){
    fastio;
    int T; cin >> T;
    for (int i = 1; i <= T; i++){
        solve(i);
    }
    return 0;
}