[C++] SWEA 1952 - 수영장

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

SW Expert Academy

<풀이>

1. 수영장 이용계획을 입력받는다.

2. 수영장 이용비용의 최소금액을 구해 출력한다.

 

<해법>

1. 문제를 접근하는 순서

=> 먼저 '모든 경우를 다 해봐야 한다.' 라는 생각을 떠올릴 수 있습니다. 따라서, 재귀를 통한 브루트포스를 구현하겠다고 생각하였습니다. 또한, 결과를 구하는 점화식을 떠올릴 수 있습니다. 최종적으로 재귀 + 메모이제이션을 이용해서 구현하였습니다.

 

#include <iostream>
#include <string.h>
#include <algorithm>
#define INF 987654321
 
using namespace std;
 
int prices[4];
int calendar[12];
int cache[12];
 
int buyTicket(int month) {
 
    //종료조건
    if (month >= 12) {
        return 0;
    }
 
    //해당 달에 이용이 없는 경우 -> 다음 달로 넘김
    if (calendar[month] == 0) {
        return buyTicket(month + 1);
    }
 
    //메모이제이션
    int& ret = cache[month];
 
    if (cache[month] != -1) {
        return ret;
    }
 
    ret = min({
        buyTicket(month + 1) + (prices[0] * calendar[month]),
        buyTicket(month + 1) + prices[1],
        buyTicket(month + 3) + prices[2],
        buyTicket(month + 12) + prices[3]
    });
 
    return ret;
}
 
int main() {
    int test_case;
    int T;
 
    cin >> T;
 
    for (test_case = 1; test_case <= T; test_case++) {
 
        //초기화
        memset(prices, 0, sizeof(prices));
        memset(calendar, 0, sizeof(calendar));
        memset(cache, -1, sizeof(cache));
        int answer = 0;
 
        //입력
        for (int i = 0; i < 4; i++) {
            cin >> prices[i];
        }
        for (int i = 0; i < 12; i++) {
            cin >> calendar[i];
        }
 
        //해법
        answer = buyTicket(0);
 
        //출력
        cout << "#" << test_case << " " << answer << "\n";
    }
 
    //종료
    return 0;
}

 

재귀함수와 메모이제이션에 대해서 알아볼 수 있는 문제였습니다.