SW Expert Academy - 1952. 수영장

문제링크

• 수영장

문제설명

• 수영장에서 판매하고 있는 이용권은 아래 4종류이다.
  • 1일 이용권: 1일 이용이 가능하다.
  • 1달 이용권: 1달 동안 이용이 가능하다. 1달 이용권은 매달 1일부터 시작한다.
  • 3달 이용권: 연속된 3달 동안 이용이 가능하다. 3달 이용권은 매달 1일부터 시작한다.
  • 1년 이용권: 1년 동안 이용이 가능하다. 1년 이용권은 매년 1월 1일부터 시작한다.
• 1년 동안 각 달의 수영장 이용 계획이 주어질 때, 가장 적은 비용으로 수영장을 이용할 수 있는 방법을 찾고 그 비용을 정답으로 출력하는 프로그램을 작성하라.

문제접근1 (테스트케이스 50개 중 45개 통과)

• 각 달에 필요한 요금을 1일 이용권으로 계산했을 때와 1달 이용권으로 계산했을 때 더 적은 비용을 선택하여 배열에 담아둔다.
• 3달 이용권을 적용했을 때와 가격이 더 저렴한 경우를 찾기 위해서 위 과정을 통해 산출된 각 달의 이용요금 배열에서 연속된 3개월을 앞에서부터 찾아 금액을 합산한다.
  • 3개월 이용권에 포함된 달의 경우 다른 3개월 이용원과 동시에 이용되면 안된다고 생각했다.
  • 즉, 1월~3월을 선택하는 경우 2~4월, 3~5월에 해당하는 3달 이용권을 구매할 수 없다고 이해하였다.
  • 따라서 1월부터 3개월을 선택하는 경우, 2월부터 3개월을 선택하는 경우, 3월부터 3개월을 선택하는 경우를 구별하여 3개월 이용권으로 이득보는 횟수가 가장 많은 조합을 찾는 과정을 추가했다.
• 3달 이용권이 적용된 달들은 무시하고, 나머지 달에 필요한 요금들과 총 필요한 3개월 이용권수를 계산하여 1년치 금액과 비교한 후 적은 비용을 선택할 수 있도록 했다.

구현

#include <iostream>
#include <climits>
#include <algorithm>
#include <memory.h>
using namespace std;

int dayFee, monthFee, threeMonFee, yearFee;
int schedule[13];
int fee[13];

// 3개월 이용요금과 비교하여 금액 계산
int updateMinimalFee() {
	int startIdx = 0;
	int cnt = 0;
	for (int start = 1; start <= 3; start++) {
		int count = 0, price = 0;
		for (int mm = start; mm <= 10; mm += 3) {
			price = fee[mm] + fee[mm + 1] + fee[mm + 2];
			if (price > threeMonFee) count++;
		}
		if (cnt < count) {
			startIdx = start;
			cnt = count;
		}
	}
	int visited[13];
	memset(visited, false, sizeof(visited));
	int price = 0;
	for (int mm = startIdx; mm <= 10; mm+=3) {
		price = fee[mm] + fee[mm + 1] + fee[mm + 2];
		if (price > threeMonFee) {
			for (int i = 0; i < 3; i++) {
				visited[mm + i] = true;
			}
		}
	}

	int tmpFee = threeMonFee * cnt;
	for (int mm = 1; mm <= 12; mm++) {
		if (visited[mm]) continue;
		tmpFee += fee[mm];
	}
	return min(tmpFee, yearFee);
}

// 1달 이용요금 기준 계산값과 비교하여 싼값으로 업데이트
void updateFeeByMonth() {
	for (int mm = 1; mm <= 12; mm++) {
		fee[mm] = min(fee[mm], monthFee);
	}
}

// 1일 이용요금 기준 계산
void updateFeeByDay() {
	for (int mm = 1; mm <= 12; mm++) {
		fee[mm] = INT_MAX;
	}

	int price = 0;
	for (int mm = 1; mm <= 12; mm++) {
		price = schedule[mm] * dayFee;
		fee[mm] = min(fee[mm], price);
	}
}


int main(int argc, char** argv)
{
	int test_case;
	int T;
	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		cin >> dayFee >> monthFee >> threeMonFee >> yearFee;
		for (int mm = 1; mm <= 12; mm++) {
			cin >> schedule[mm];
		}

		updateFeeByDay();
		updateFeeByMonth();
		int ans = updateMinimalFee();
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

문제접근2 (Pass)

• DP 로 푼 사람들의 풀이를 참고하였다.
• 매순간 최적의 선택을 하며 12월까지 최종 이용요금을 계산해가는 방법이다.
• 문제접근1 처럼 풀었던 경우 가장 애매했던 부분이 3개월 이용권을 적용하는 방법이 너무 다양하다는 것이었다. 이런 다양성 때문에 완전탐색처럼 문제를 풀 수 밖에 없었는데 DP 는 이러한 고민을 너무나 쉽게 해결한다.
• dp[month] 는 month 달까지 수영장을 이용하는데 드는 최소 비용을 담는다.

  // 3가지 방법에 대한 최소비용을 담는 로직
  // 3개월 이용권에 대한 최적의 선택을 매번 할 수 있게 된다.
  dp[month] = min( {dp[month-1] + plan[month]*dayFee, dp[month-1] + monthFee, dp[month-3] + threeMonthFee} );
  

구현

#include <iostream>
#include <climits>
#include <algorithm>
#include <memory.h>
using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
	 // freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int dayFee, monthFee, threeMonFee, yearFee;
		int schedule[13];
		int dp[13];
		cin >> dayFee >> monthFee >> threeMonFee >> yearFee;
		for (int mm = 1; mm <= 12; mm++) {
			cin >> schedule[mm];
		}
		dp[0] = 0;
		dp[1] = min(schedule[1] * dayFee, monthFee);
		dp[2] = min(dp[1] + schedule[2] * dayFee, dp[1] + monthFee);
		for (int mm = 3; mm <= 12; mm++) {
			dp[mm] = min({ dp[mm-1] + schedule[mm] * dayFee, dp[mm-1] + monthFee, dp[mm - 3] + threeMonFee });
		}
		int ans = min(dp[12], yearFee);
		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}