Greedy Algorithm - [백준 문제 : 10162] 전자레인지 풀이

 

 

 

 

 

 

 

우선 A, B, C로 각각 다른 조리 시간 버튼의 조합으로 T(요리시간)을 정확하게 맞출 수 있냐?

만약 맞출 수 있다면 A번 누른 횟수, B번 누른 횟수, C번 누른 횟수를 출력하라는 문제입니다. 

 

 

<C++>

// Example program
#include <iostream>
#include <string>

using namespace std;
int main()
{

	//결과값:최소 기능 사용 횟수
	int Acount = 0;
	int Bcount = 0;
	int Ccount = 0;

	// 전자레인지 도구(단위:second)
	int A = 300;
	int B = 60;
	int C = 10;

	//요리시간 T
	int T = 0;

	//불가능 여부 체크 flag
	bool impossibleFlag = false;

	cin >> T;

	while (T != 0)
	{

		if (T >= A)
		{
			//A기능 사용 나눈 몫
			Acount = T / A;
			//A기능 사용 후 나머지
			T = T % A;

		}
		else if (T >= B) {
            
			// B기능 사용 나눈 몫
			Bcount = T / B;
            // B기능 사용 후 나머지
			T = T % B;

		}
		else if (T >= C) {

            // C기능 사용 나눈 몫
			Ccount = T / C;
            // C기능 사용 후 나머지
			T = T % C;
		}
		else
		{

			if (T != 0)

			{
				// A,B,C로 계속 나눴지만 나머지가 남아
				// T 를 나누기 불가능한 경우
				impossibleFlag = true;
				break;
			}
		}
	}

	//T 나누기 불가능 여부 체크 후 
	//각각 결과 값 출력 분기문
	if (impossibleFlag == true)
	{
		cout << -1 << endl;
	}
	else {
		cout << Acount << " " << Bcount << " " << Ccount << endl;

	}
}

 

<Python>

# T 요리시간 단위 초
T = int(input())

# 조리시간 A,B,C도 초 단위로 맞춤
A = 300
B = 60
C = 10


#A,B,C각각의 count를 저장할 변수
A_cnt = 0;
B_cnt = 0;
C_cnt = 0;

#A,B,C로 나누어 떨어지지 않을 경우를 위한 flag
impossible_flag = False

while T != 0:
    
    
    if T >= A:
        A_cnt = int(T/A)
        T = T%A
    
    elif T>= B:
        B_cnt = int(T/B)
        T = T%B
    elif T>= C:
        C_cnt = int(T/C)
        T = T%C
    else:
        if T!= 0:
            impossible_flag = True
            break
        
if impossible_flag == True:
    print(-1)
else:
    print(A_cnt, B_cnt, C_cnt)