재귀함수를 이용한 완전탐색의 기본에 대해서 (2)

'재귀함수를 이용한 완전탐색의 기본에 대해서 (1)' 에서는 간단하게 숫자 조합을

고르는 방법에 대해서 알아 보았습니다.

 

사실 이것만 알면 그보다 좀 더 어려운 문제들 푸는 모든 준비는 끝났지만, 응용하는

방법을 알아보기로 합시다.

 

 

https://www.acmicpc.net/problem/13302

13302번: 리조트

 

위 문제는 DP 문제 입니다.

DP 문제를 푸는 방법에는 두 가지가 있습니다.

 

1. bottom-up

2. top-down

 

DP를 푸신 분들의 코드를 살펴보면 bottom-up 방식이 많이 보입니다

각 방법의 장단점이 있으므로, 어떤 경우에 어떤 것이 좋다 말하는 것은 DP 글에서 다루도록 하겠습니다.

 

이 문제를 꺼낸 이유는 top-down 방식으로 풀 때, 재귀 함수를 이용한 완전 탐색이 기본 코드 골격을

구성하기 때문입니다.

 

 DP top-down 풀이 대한 설명은 하지 않을 것이고, 완전 탐색하는 것까지 구현해 볼 것입니다.

 

 

재귀 함수의 구성에 대해서 알아봅시다.

 

 

 

1. parameter

보통 재귀 함수에서 현재 재귀 함수의 depth나 위치를 의미하는 parameter를 가지게 됩니다.

즉, 현재 함수의 상태를 의미하는 parameter를 항상 가지고 있습니다.

 

왜 parameter가 필요할까요?

- termination condition(종료 조건) : 더이상 탐색할 필요가 없음을 알리는 조건

- 현재 상태를 알 수 있어야 알맞은 다음 상태를 탐색할 수 있기 때문입니다

 

이 문제에서 cur과 coupon을 의미합니다. cur은 현재 몇 일인가를 의미하는 변수입니다.

coupon은 현재 가지고 있는 coupon의 갯수입니다.

 

 

 

 

2. action

문제에서 각 함수의 상태에서 어떤 행위를 할 수 있는지 주어집니다.

 

예)

- 휴가를 3일 또는 5일을 사용한다. 

- 자전거 또는 자동차를 탄다.

- 2로 또는 3으로 나눈다.

 

이러한 행위들을 현재 상태에 연산을 가해주어, 다음 상태를 탐색 시도하면 됩니다.

 

이 문제 설명이 조금 복잡하긴 하지만, 각 스텝에서 취할 수 있는 액션에 대해서 생각해 보겠습니다.

 

if ( 현재 날이 리조트를 이용할 수 없는 날일 경우 )

   1. 아무 액션을 취하지 않고 다음 날로 넘어간다

 

else 

   1. 1일치 리조트 이용권을 끊는다

   2. 3일치 리조트 이용권을 끊는다

   3. 5일치 리조트 이용권을 끊는다

   4. if( 쿠폰이 3개 이상이라면 ) 하루 공짜로 리조트 이용한다

 

 

 

 

3. return value

이 부분이 재귀함수를 사용할 때, 가장 어려워하는 부분 중에 하나 입니다.

 

꼭 리턴값을 돌려주어야 하는가, 돌려준다면 어떤 값을 주어야 하는가.

 

반드시 리턴값을 돌려주어야 하는 것은 아닙니다. 문제에 따라서 다릅니다.

정답을 저장하는 변수를 전역변수로 선언해 놓고 모든 상태를 탐색하면서 전역 변수를 갱신하면서 정답을 

찾아 나가도 됩니다.

 

코드를 좀 더 깔끔하게 짜고 싶거나, 복잡한 구조를 짜고 싶다면 리턴값에 대해서 명확히 알아야 합니다.

괜히 모르는데 리턴값을 주었다가 오답이 나올 수도 있습니다.

 

리턴값을 위해서 가장 중요한 것은 '명확한 정의' 입니다.

리턴값의 시작점인 termination condition 에서 어떤 값을 돌려주어야 하는지부터 명확한 논리가 필요합니다.

 

0 을 돌려주어야 하는지, 1을 돌려주어야 하는지 혹은 매우 작은값 -1234567890, 매우 큰값 1234567890 등등

여러가지 경우가 있습니다. 

 

이렇게 명확히 정의하고, 논리가 흐트러짐 없이 밀고 나아간다면,

이 리턴값을 받아서 무엇을 할 것인지에 대해서 더 명확히 짤 수 있습니다.

 

이 문제에서 리턴값의 정의는 '리조트에 입장하기 위해서 지불해야 하는 비용의 최솟값' 입니다.

 

이 문제의 코드를 통해서 보겠습니다.

 

 

ret = min(ret, sol(cur + 1, coupon) + 10000);        // 리조트 1일치 끊는다

 

코드를 봅시다.

 

sol(cur + 1, coupon)의 의미

현재 상태(cur, coupon는 구체적인 어떤 값을 가지고 있겠죠) 에서 리조트 1일치를 끊었을 때 이후의 리조트 입장하기 위한 최소 비용값

 

+ 10000 의 의미

(리조트 1일치를 끊었을 때 이후의 최소 비용값) + (현재 리조트 1일치 사용 비용) = (현재 리조트 1일치 사용했을 경우의 최소 비용값)

 

이런식으로 현재 1일치 / 3일치 / 5일치 끊었을 경우의 최소값을 구해서 리턴하면 됩니다.

 

#include <bits/stdc++.h>
 
using namespace std;
 
int n, m;
bool chk[101];    // 리조트 이용 못하는 날을 기록하기 위한 배열
 
int sol(int cur, int coupon) {        // 현재 날과 현재 쿠폰 갯수를 저장한다. 이 부분은 매우 중요하다! 
    if (cur >= n + 1) return 0;        // 여름방학 기간이 모두 끝났다면 리턴한다
 
    int ret = 1234567890;            // 최소값을 구하기 위해 나올수 없는 큰 값으로 세팅
    if (chk[cur]) ret = min(ret, sol(cur + 1, coupon));    // 리조트 이용 못하는 날이므로 그냥 넘어간다
    else {
        ret = min(ret, sol(cur + 1, coupon) + 10000);        // 리조트 1일치 끊는다
        ret = min(ret, sol(cur + 3, coupon + 1) + 25000);    // 리조트 3일치 끊는다
        ret = min(ret, sol(cur + 5, coupon + 2) + 37000);    // 리조트 5일치 끊는다
        if(coupon >= 3) ret = min(ret, sol(cur + 1, coupon - 3));    // 쿠폰이 3개 이상이면, 리조트 1일을 공짜로 이용한다
    }
 
    return ret;
}
 
 
int main() {    
    cin >> n >> m;
    
    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        chk[a] = true;
    }
    cout << sol(1, 0);
}