koi : 앱(small)

http://koistudy.net/?mid=prob_page&NO=2270&SEARCH=0

KOISTUDY

 

#include <iostream>
 
int n, M, m[101], c[101];
 
//int minimum_cost = 987654321;
 
constexpr int min(int first, int second)
{
    return (((first < second) ? first : second));
}
 
void input()
{
    std::cin >> n >> M;
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> m[i];
    }
    for (int i = 1; i <= n; ++i)
    {
        std::cin >> c[i];
    }
}
 
int f(int i, int r)
{
    if (i == 0)
    {
        if (r <= 0)
        {
            return 0;
        }
        else
        {
            return 987654321;
        }
    }
    else if (r <= 0)
    {
        return f(i - 1, r);
    }
    else
    {
        int a = f(i - 1, r - m[i]) + c[i];
        int b = f(i - 1, r);
        //std::cout << i << ' ' << r << '\t' << a << ' ' << b << '\n';
        return min(a, b);
    }
}
 
int main()
{
    input();
    std::cout << f(n, M);
    return 0;
}

적당히 꼬아놓은 재귀는 참 짜증나는 것 같다

 

사실 이정도 재귀는 금방금방 이해할수잇어야할텐데

 

아무튼, 흐름은 다음과 같다

 

int f(int i, int r)
{
    //앱을 다 순회한 경우
    if (i == 0)
    {
        //메모리를 확보한 경우
        if (r <= 0)
        {
            return 0;
        }
        //메모리를 확보하지 못한 경우
        else
        {
            return 987654321;
        }
    }
    else if (r <= 0)
    {
        //앱을 다 순회하지 않았지만 메모리를 확보한 경우, 0을 리턴하기 위해 i를 계속 돌린다.
        return f(i - 1, r);
    }
    else
    {
        //앱을 비활성화 하는 경우, 계속된 재귀로 메모리를 확보한다면 0을 계속 리턴하게 될 것인데
        //재귀의 종료조건을 달성하는 순간 비활성화된 모든 앱의 비용을 더하면서 재귀가 풀린다.
        //그렇게 된다면 a는 해당 메모리들의 비활성화 비용을 합친 값을 가지게 된다.
        int a = f(i - 1, r - m[i]) + c[i];
        //앱을 비활성화 하지 않는 경우
        //다음 앱을 살펴보는 역할을 하거나, 확보해야할 메모리를 건드리지 않기 때문에 9876...을
        //리턴한다. 결과적으로 min에 의해 a의 값을 갖게 된다.
        int b = f(i - 1, r);
        //std::cout << i << ' ' << r << '\t' << a << ' ' << b << '\n';
        return min(a, b);
    }
}

 

글로 써놔도 직접 돌려보기 전에는 이해가 힘들다.

 

한줄씩 살펴보는 것이 이해와 정신건강에 좋을 것.

 

순열이나 마찬가지다.

 

1 2 3 4 5를

 

1

2

...

5

12

13

...

45

123

124

...

345

1234

1235

2345

12345

 

모든 경우를 살펴보는 것이다.

 

여기서 만약 메모리를 확보하게 된다면

 

    else if (r <= 0)

    {

        //앱을 다 순회하지 않았지만 메모리를 확보한 경우, 0을 리턴하기 위해 i를 계속 돌린다.

        return f(i - 1, r);

    }

 

123에서 메모리를 확보했다면 123은 a에서 값을 갖는다

 

그리고 int b = f(i - 1, r);에서 124로 넘어가게 된다.

 

사실 코드를 잘 살펴보면 순서가 반대인것을 알수잇다

 

정확한 순회 순서는 다음과 같다

 

 

이러한 순서인 것이다.