/* 16:44분 가장 적은 비용으로 수영장을 이용 1일이용 1달 이용 매달 1일부터시작 3달 이용권 3달 매달 1일이부터 시작 11월 12월에다 3달 이용권 가능 1년 이용권 며년 1일1부터 시작합니다. 매년 1월 1일만 살 수 잇는 것인가? 각 달의 이용 계획은 테이블의 형태로 수립 각 이용권의 요금과 각 달의 이용 계획이 입력. 예시를 보면, 1일 이용권 1달 이용권 3달 이용권 1년 이용권 가격이 나오고 가장 적은 경우 오꼐이 모두 1일 이용권 모두 1달 이용권 3월 1일 이용권 456월은 3달 이용권 가장 적은 비용으로 수영장을 이용한 경우 4번의 경우 정답은 110 원 dfs 문제로 풀어보도록 하겠습니다. if return pos, depth 가져가야하는 파라미터를 정확하게 알기. 경우의 수를 보면 1. 모두 1일 이용권으로 이용하는 방법 2. 모두 1달 이용권으로만 이용하는 방법 3. 1년 이용권으로 이용하는 방법 4. 1일 이용권과 1달 이용권을 섞어서 사용하는 방법 (몇달은 1일 이용권, 나머지 달은 1달 이용권) 여기서 2가지의 경우의 수가 있습니다. */ #include <iostream> #include <algorithm> using namespace std; int T; int minVal = 1000000000; int P[4]; // 1일 1달 3달 1년 이용권 가격 저장하는 배열 int M[13]; // 1월부터 12월까지 각 달에 이용 계획 int only_day; int only_month; int only_year; int mix; int ava_day; int ava_month; int only_min; void problemIn() { for (int i = 0; i < 4; i++) { cin >> P[i]; } for (int i = 1; i < 13; i++) { cin >> M[i]; ava_day += M[i]; if (M[i] > 0) { ava_month++; } } } void only() { only_year = P[3]; // 일년 이용권 only_month = ava_month * P[1]; // 모두 한달 이용권 only_day = ava_day * P[0]; // 모두 일이용권 if (only_year > only_month) only_min = only_month; else only_min = only_year; if (only_year > only_day) only_min = only_day; // only_min 이 가장 작은값 } /* 1일, 1달, 3달 이용권 믹스 해야합니다. 자 예제 3번의 경우 3월 1일 이용권, 4번의 경우 1일 이용권 과 1달 이용권 12월이 끝이 아니라, 사용하는 날까지만 사용하면 됩니다. 1달 이용권과 1일 이용권은 단순 계산하면 되고, 1달 이용권과 3달 이용권 사이에 비교만 하면 됩니다. i=2; 경우의 수가 3가지로 나뉩니다. 1일 1달 3달 */ void dfs(int month, int price_sum) { // 달과 값
if (month >= 13) { if (price_sum < minVal) minVal = price_sum; return; }
dfs(month + 1, price_sum + P[0]*M[month]); // 한달을 1일이용권으로 했을 때 가격을 넣어줌 dfs(month + 1, price_sum + P[1]); // 한달을 plus 했을 때 가격 넣어줌. dfs(month + 3, price_sum + P[2]); } int main(void) { cin >> T; for (int i = 1; i <= T; i++) { minVal = 1000000000; problemIn();
only(); for (int i = 1; i < 13; i++) { // 시작달을 넣어줍니다. if (M[i] > 0) { dfs(i, 0); break; } } minVal = min(minVal, only_min); cout << "#" << i << " " << minVal << endl; } return 0; } |
dfs로 돌리는 문제인데, return 구문을 넣어주면 됩니다. |