수영장_1952

문제 출처 : 수영장_1952

파라미터 정리

T 테스트 케이스 개수
이용권 종류 :
1일 이용권-1일 이용 가능
1달 이용권-1달 동안 이용 가능, 매달 1일부터 시작
3달 이용권-연속된 3달 동안 이용 가능, 매달 1일부터 시작, 해가 바뀌면 사라짐
1년 이용권-1년 동안 이용 가능, 매년 1월 1일부터 시작
원하는 것 = 각 이용권의 요금과 각 달의 이용 계획이 주어질 때, 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 비용을 출력하기

간략한 과정

input_1 T 입력받기
input_2 {각 이용권의 가격 4개,
각 달 마다 이용 계획 12달} x T만큼 입력받기
DP를 이용한 알고리즘을 테스트 케이스만큼 실행함{
각 달마다 1일 이용권으로 결제했을 때 소요되는 금액 계산
모든 달에 대해 1달 이용권,1일 이용권 총 요금 중 최솟값 비교
123,234,345,456,567,678,789,8910,91011,101112,1112,12 을 선택했을 때 발생하는 금액과 현재 최솟값 비교
현재 계산된 총 요금과 1년 이용권 금액 최솟값 비교
테스트 케이스 숫자와 최솟값 출력
}
output "#n" + "각 케이스마다 비용을 가장 적게 지출하는 비용" 반환하기

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define INF 9845651

struct cost{
  int n1,n2,n3,n4;  
};
int T;
vector<cost> ticket;
int sched[50][12];

void solve(){
    int cnt = 0;
    
    do{
        int res = INF;
        int sum[13] = {0};
        //각 케이스의 요금권
        cost n_cost = ticket[cnt];
        //각각의 경우 실행하고 최솟값 갱신
        //1일권 만 사용했을 때 vs. 1달권이랑 비교
        int n_mon[12];
        for(int i = 0; i < 12; i++){
            int mon = sched[cnt][i];
            n_mon[i] = min(n_cost.n1*mon, n_cost.n2);
        }
        //3달 마다 이전값이랑 비교
        for(int  i = 1; i < 13; i++){
            sum[i] = sum[i-1] + n_mon[i-1];
            if(i-3 >= 0)
                sum[i] = min(sum[i], sum[i-3] + n_cost.n3);
        }
        //1년 이용권이랑 비교
        res = min(n_cost.n4, sum[12]);
        //최솟값 출력
        cout << "#" << cnt+1 << " " << res << endl;
        //다음 케이스로 넘어감
        cnt++;
    }while(cnt!=T);
    
    
    return;
}

int main()
{
    cin >> T;
    for(int i = 0; i < T; i++){
        int x,y,z,a;
        cin >> x >> y >> z >> a;
        ticket.push_back({x,y,z,a});
        for(int k = 0; k < 12; k++)
            cin >> sched[i][k];
    }
    solve();
    
    return 0;
}

시행착오

T= 1, 예제
1
10 40 100 300
0 0 2 9 1 5 0 0 0 0 0 0

백업_0531_pm2:30
구현 완료, T =1인 예제 통과함
SWEA 제출 결과 FAIL 나옴
문제점 : 3달 이용권을 한번만 선택해서 문제가 발생함
3달 이용권을 여러 달 선택할 수 있게 바꾸기

        //3달 마다 이전값이랑 비교
        int sub_sum = INF;
        for(int k = 0; k < 12; k++){
            int temp = 0;
            if(k == 10){
                temp = n_mon[k] + n_mon[k+1];
            }else if(k == 11){
                temp = n_mon[k];
            }else
                temp = n_mon[k] + n_mon[k+1] + n_mon[k+2];    
           temp = sum - temp + n_cost.n3;
           if(temp < sum) sub_sum = min(sub_sum, temp);
        }
        sum = min(sub_sum, sum);