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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq&categoryId=AV5PpFQaAQMDFAUq&categoryType=CODE

SW Expert Academy

 

최종 코드

• GitHub -> https://github.com/hwayeon351/SWEA-Algorithms/blob/main/SWEA1952.cpp

GitHub - hwayeon351/SWEA-Algorithms: SWEA 알고리즘 소스 코드 모음

//
//  main.cpp
//  SWEA1952_1
//
//  Created by Hwayeon on 2021/10/15.
//

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

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    
    int dp[13] = {0, };
    int day, month, three_month, year;
    int plan[13] = {0, };
    for(test_case=1; test_case<=T; ++test_case){
        memset(dp, 0, sizeof(dp));
        cin >> day >> month >> three_month >> year;
        for(int m=1; m<=12; m++){
            cin >> plan[m];
        }
        dp[1] = min({day*plan[1], month});
        dp[2] = min({dp[1]+day*plan[2], dp[1]+month});
        for(int m=3; m<=12; m++){
            dp[m] = min({dp[m-1]+day*plan[m], dp[m-1]+month, dp[m-3]+three_month});
        }
        if(dp[12] > year) dp[12] = year;
        cout << "#" << test_case << " " << dp[12] << endl;
    }
    return 0;
}

 

---

풀이 과정

풀이 시간 20분

• DP 알고리즘 적용

 

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

int main(int argc, const char * argv[]) {
    int test_case;
    int T;
    cin >> T;
    
    //dp[i] -> 1~i까지 최소 수영장 이용 금액
    int dp[13] = {0, };
    
    //day = 1일 이용권 금액, month = 1달 이용권 금액, three_month = 3달 이용권 금액, year = 1년 이용권 금액
    int day, month, three_month, year;
    
    //play[m] = m달의 수영장 이용 계획
    int plan[13] = {0, };
    
    for(test_case=1; test_case<=T; ++test_case){
    	//dp 초기화
        memset(dp, 0, sizeof(dp));
        cin >> day >> month >> three_month >> year;
        for(int m=1; m<=12; m++){
            cin >> plan[m];
        }
        
        //dp 구하기
        dp[1] = min({day*plan[1], month});
        dp[2] = min({dp[1]+day*plan[2], dp[1]+month});
        for(int m=3; m<=12; m++){
        	//1일 이용권을 이용하는 경우, 1달 이용권을 이용하는 경우, 3달 이용권을 이용하는 경우 중 가장 적은 금액이 dp[m]이다
            dp[m] = min({dp[m-1]+day*plan[m], dp[m-1]+month, dp[m-3]+three_month});
        }
        //1년 이용권을 이용하는 것이 더 저렴한 경우,
        if(dp[12] > year) dp[12] = year;
        cout << "#" << test_case << " " << dp[12] << endl;
    }
    return 0;
}
//시간복잡도 = O(T), 공간복잡도 = O(1)

---

이전 풀이

풀이 시간  46분

 

1. 완전 탐색 > DFS

DFS 함수

 1월부터 12월까지 1일 이용권, 1달 이용권, 3달 이용권을 구매했을 때의 모든 경우의 수를 탐색한다.

이용일이 0일인 경우에는, 재귀를 통해 다음 달을 탐색 하도록 하고 12월까지 탐색한 후에 탐색을 종료한다.

 

2. minimum_cost 초기화

1.에서 12월까지 탐색한 후에는 전역변수인 minimum_cost와 탐색하는 동안 발생한 now_cost를 비교한다. 또한, 1일, 1달, 3달 이용권을 구매한 경우만 계산하였다.

따라서, 각 test_case에서의 cost배열을 초기화 한 이후에 1년 이용권 요금으로 minimum_cost를 초기화하도록 한다.

 

 

---

오답 노트

 

 처음 문제를 접했을 때 나는 3달 이용권은 3달 연달아서 이용일이 있는 경우만을 따졌었다.

예를 들어, 

1월	2월	3월	4월	5월	6월	7월	8월	9월	10월	11월	12월
0일	0일	2일	9월	1일	5일	0일	0일	0일	0일	1일	1일

이용 계획이 위와 같다면, 3달 이용권을 사용할 수 있는 경우의 수는 3-5월, 4-6월, 11-12월(예외), 12월(예외)이다.

 각 경우의 수마다(3개월) 3달 이용권, 1달 이용권, 1일 이용권 중 어느 것을 구매해야 저렴한지를 또 따져주었다.

이렇게 접근했었던 이유는 연달아 3달 동안 이용계획이 없는 경우는 3달 이용권을 구매할 수 없는 줄 알았다.

 즉, 문제 이해를 잘 못했던 것!

따라서 이용일이 있는 날에 구매 가능한 이용권의 경우의 수를 따져서 해결하려 했었다.

결국, 일일이 코드로 경우를 따지다 보니 매우 복잡했고 2시간동안 뻘짓을 하게 되었다.

 

---

참고

• 2021/01/11 - [C++] - [알고리즘] BFS와 DFS

[알고리즘] BFS와 DFS