지불해야 할 루피 금액(pay_rupees)이 주어져 있고, 액면가가 각각 Rupees_amount_1과 Rupees_amount_2인 두 종류의 지폐를 무한히 보유하고 있다고 가정해 보겠습니다. 목표는 정확히 distribution_total장의 지폐만 사용하여 pay_rupees를 지불하는 것이며, 이때 필요한 Rupees_amount_1 지폐의 장수를 계산하는 것입니다. 만약 조건에 맞게 지불할 방법이 없다면 −1을 답으로 반환해야 합니다.
입력 예시
Rupees_amount_1 = 1, Rupees_amount_2 = 5, pay_Rupees = 11, distribution_total = 7
출력
필요한 지폐의 장수: 6
설명
6×1 + 5×1 = 11이며, 지폐는 6 + 1 = 7장입니다.
입력 예시
Rupees_amount_1 = 2, Rupees_amount_2 = 3, pay_Rupees = 10, distribution_total = 4
출력
필요한 지폐의 장수: 2
설명
2×2 + 3×2 = 10이며, 지폐는 2 + 2 = 4장입니다.
풀이 접근 방식
Rupees_amount_1 지폐의 장수를 a1, 사용하는 전체 지폐 장수를 N이라고 하겠습니다. 금액 P를 지불하기 위해 다음과 같은 방정식을 세울 수 있습니다.
- a1 × Rupees_amount_1 + (N − a1) × Rupees_amount_2 = P
- P = a1 × Rupees_amount_1 + N × Rupees_amount_2 − a1 × Rupees_amount_2
- P − N × Rupees_amount_2 = a1 × (Rupees_amount_1 − Rupees_amount_2)
- a1 = (P − N × Rupees_amount_2) ÷ (Rupees_amount_1 − Rupees_amount_2)
따라서 a1이 정수일 때만 해가 존재하고, 나누어떨어지지 않으면 −1을 반환합니다. 이 방법은 단순 연산만 사용하므로 시간 복잡도는 O(1)로 매우 효율적입니다.
알고리즘 단계
- 모든 값을 입력으로 받습니다.
- notes_needed(int Rupees_amount_1, int Rupees_amount_2, int pay_Rupees, int distribution_total) 함수가 모든 입력을 받아 필요한 지폐 장수를 반환합니다.
- count 변수를 0으로 초기화합니다.
- total = pay_Rupees − (Rupees_amount_2 × distribution_total)을 계산합니다.
- total_given = Rupees_amount_1 − Rupees_amount_2로 설정합니다.
- total % total_given == 0이면 count를 total / total_given 값으로 설정하여 반환합니다.
- 그렇지 않으면 −1을 반환합니다.
C++ 코드 예제
#include<bits/stdc++.h>
using namespace std;
int notes_needed(int Rupees_amount_1, int Rupees_amount_2, int pay_Rupees, int distribution_total){
int count = 0;
int total = pay_Rupees - (Rupees_amount_2 * distribution_total);
int total_given = Rupees_amount_1 - Rupees_amount_2;
if (total % total_given == 0){
count = total / total_given;
return count;
} else {
return -1;
}
}
int main(){
int Rupees_amount_1 = 1;
int Rupees_amount_2 = 5;
int pay_Rupees = 11;
int distribution_total = 7;
cout<<"Count of number of currency notes needed are: "<<notes_needed(Rupees_amount_1, Rupees_amount_2, pay_Rupees, distribution_total);
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
Count of number of currency notes needed are: 6