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

문제

SWEA 모의 SW 역량테스트 - 1952 수영장

SW Expert Academy

 

---

문제 풀이

접근 방식

1일권 / 1달권 /  3달권/ 1년권의 조합으로 가능한 최소 비용을 구하는 문제이다.

우선, 1일권과 1달권을 먼저 비교해주었고, 그 값과 3달권을 비교하여 더 나은 선택을 찾아주었다.

마지막으로 그 결과와 1년권의 가격을 비교하여 최종적인 최소 비용을 구하였다.

 

1) 1일권과 1달권

 

각 달의 이용 계획 일수를 days 벡터에 입력받고,

(계획 일수) × (1일권의 가격)과 1달권의 가격 중 더 낮은 가격을 선택하여 저장해주었다.

그리고 모든 달의 비용의 총합(total)도 구해주었다.

 

 

2) 3달권

 

위에서 구한 각 달의 최소 비용과 총 비용, 3달권의 가격을 이용하여 DP로 최소 비용을 구하였다.

result[i]에는 i+1번째 달에서 최선의 선택을 했을 때의 총 비용을 저장해주었다.

즉, 3달권의 가격에서 i+1 달부터 3달 동안의 비용을 빼주고, 그 값(diff)이 음수이면 3달권을 선택하도록 하였다.

3달권을 선택하게 되면, 총 비용(total)에서 diff를 더해준 값을 result[i]에 저장해주었다.

total 값은 3달 이전의 결괏값(result[i-3])이 존재하면,

그 값으로 매번 바꿔주었고(3달권은 3달 간격으로 살 수 있기 때문에),

위의 결과보다 result[i-1]의 값이 더 낮다면, 이 값을 result[i]에 저장해주었다.

이 과정을 거치면 result[11]에는 12달을 모두 탐색한 최선의 결과 비용이 저장된다.

(1일권, 1달권, 3달권만 고려했을 때의 최소 비용)

 

3) 1년권

 

위에서 구한 결과와 1년권의 가격을 비교하여 최종적인 최소 비용을 구하였다.

 

---

풀이 코드 - C++

#include <iostream>
 
using namespace std;
 
int main(int argc, char** argv)
{
    int test_case;
    int T, total, answer;
    int price[4];
    int days[12];
    int result[12];
    // freopen("input.txt", "r", stdin);
    cin >> T;
    for (test_case = 1; test_case <= T; ++test_case) {
        // 입력 받기 & 1일권과 1달권 비교 & 비용 총합 구하기
        total = 0;
        for (int i = 0; i < 4; i++)  {
            cin >> price[i];
        }
        for (int i = 0; i < 12; i++) {
            cin >> days[i];
            if (days[i] * price[0] <= price[1])
                days[i] = days[i] * price[0];
            else
                days[i] = price[1];
            total += days[i];
        }
 
        // 3달권과 비교
        for (int i = 0; i < 12; i++) {
            int diff = price[2];
            for (int j = i; j < i + 3; j++) {
                if (j == 12) break;
                diff -= days[j];
            }
 
            if (i - 3 >= 0)
                total = result[i - 3];
             
            if (diff < 0)    // 3달권 O
                result[i] = total + diff;
            else            // 3달권 X
                result[i] = total;
             
            if(i > 0 && result[i] > result[i - 1])
                result[i] = result[i - 1];
        }
        answer = result[11];
 
        // 1년권과 비교
        if (answer > price[3])
            answer = price[3];
 
        cout << "#" << test_case << " " << answer << endl;
    }
    return 0;
}

실행 결과