주어진 금액으로 제품을 구매할 수 있는지 확인하는 C++ 프로그램

숫자 N이 하나 주어져 있다고 가정해 봅시다. 어떤 케이크 가게에서는 케이크를 40루피에, 도넛을 70루피에 판매하고 있습니다. 우리가 확인해야 할 것은 정확히 N루피를 사용해 이 제품들을 구매할 수 있는지 여부입니다.

예를 들어 입력이 N = 110이라면 출력은 True가 됩니다. 케이크 한 개(40루피)와 도넛 한 개(70루피)를 구매하면 40 + 70 = 110루피가 되기 때문입니다.

문제 해결 접근 방식

이 문제는 깊이 우선 탐색(DFS)을 활용해 해결할 수 있습니다. 현재까지 계산한 금액 i에서 시작하여, 매 단계마다 케이크(40루피)를 추가하는 경우와 도넛(70루피)을 추가하는 경우를 재귀적으로 탐색합니다. 금액이 정확히 n과 일치하면 true를 반환하고, n을 초과하면 false를 반환합니다.

구체적인 해결 단계는 다음과 같습니다.

결과를 저장할 불리언 변수 o를 false로 초기화합니다.
현재 금액 i를 인자로 받는 dfs() 함수를 정의합니다.
i가 n보다 크면 false를 반환합니다.
i가 n과 같으면 true를 반환합니다.
dfs(i + 40)이 true이면 true를 반환하고, 그렇지 않으면 dfs(i + 70)의 결과를 반환합니다.
메인 메서드에서 n에 N을 대입한 후 dfs(0)을 호출하여 최종 결과를 얻습니다.

o := false
Define a function dfs(), this will take i,
if i > n, then:
    return false
if i is same as n, then:
    return true
if dfs(i + 40), then:
    return true
return dfs(i + 70)
From the main method, do the following
n := N
o := dfs(0)
return o

예제

더 나은 이해를 돕기 위해 다음 구현 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int n;
bool o = false;

bool dfs(int i) {
   if (i > n)
      return false;
   if (i == n)
      return true;
   if (dfs(i + 40))
      return true;
   return dfs(i + 70);
}
bool solve(int N) {
   n = N;
   o = dfs(0);
   return o;
}
int main(){
   int N = 110;
   cout << solve(N) << endl;
}