koi : 예산관리

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

KOISTUDY

 

#include <iostream>
 
int B;
int n;
int arr[22];
int max_val = 0;
 
constexpr int max(int first, int second)
{
    return first > second ? first : second;
}
 
void input()
{
    std::cin >> B >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
    }
}
 
void solve(int cur, int money)
{
    if (money <= B)
    {
        max_val = max(money, max_val);
    }
    else
    {
        return;
    }
    if (cur == n)
    {
        return;
    }
 
    for (int i = cur; i < n; ++i)
    {
        solve(i + 1, money + arr[i], i);
    }
}
 
void output()
{
    std::cout << max_val;
}
 
int main()
{
    input();
    solve(0, 0, 0);
    output();
    return 0;
}

클래식한 문제

 

끝구간을 자꾸 건너뛰어버려서 당황했다.

 

기초가 가장 중요한 법이지..

 

#include <iostream>
 
int B;
int n;
int arr[22];
int max_val = 0;
 
constexpr int max(int first, int second)
{
    return first > second ? first : second;
}
 
void input()
{
    std::cin >> B >> n;
    for (int i = 0; i < n; ++i)
    {
        std::cin >> arr[i];
    }
}
 
void func(int i, int sum)
{
    if (i == n)
    {
        if (sum <= B && sum > max_val)
        {
            max_val = sum;
        }
        return;
    }
 
    func(i + 1, sum + arr[i]);
    func(i + 1, sum);
}
 
void output()
{
    std::cout << max_val;
}
 
int main()
{
    input();
    func(0, 0);
    output();
    return 0;
}

교재상의 정답

 

배열이 최대 21개라 가능하겠지만...

 

재귀의 근-본이라는 느낌이라고 해야하나

 

이렇게 정의를 설계해서 짜는게 진짜 재귀를 쓰는 실력이 아닌가 한다

 

난 그냥 막 짜는데...