[백준] 2839 C++

문제설명

입출력 예제

개념

　N이 주어졌을 때, 주어진 3kg 봉지와 5kg 봉지를 이용해 3x + 5y = N을 만족하는 최소의 정수쌍의 합을 구하는 문제다. 이때 이러한 해를 만족하는 정수쌍이 존재하지 않을 때는 -1을 출력해야 하며, x나 y에 0이 들어갈 수 있다는 것을 유념해야 한다.

 

알고리즘

　필자의 경우엔 3x + 5y = N을 y에 대해 정리하여 y = -3x/5 + N/5로 표현한 뒤, 다음과 같은 과정으로 문제를 풀었다.

• x = 0부터 y = -3x/5 + N/5가 정수가 되는 (x,y)의 값을 찾고, 배열에 x + y를 넣음 (개수를 묻는 문제이므로)
• 만약 -3x/5 + N/5 < 0이 되면 더이상 0을 넘는 값을 찾을 수 없음
• 일련의 과정을 통해 x + y의 값을 배열에 넣은 후, 배열이 비어있으면 -1을 출력하고, 아니면 최솟값을 출력

 

풀이

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int N;
    cin >> N;

    vector<int> ans;
    
    int x = 0;
    float check = (float)(-3 * x + N) / 5;

    while (true)
    {
        if (check < 0)
            break;

        else
        {
            check = (float)(-3 * x + N) / 5;

            if (check - (int)check == 0)
            {
                ans.push_back(x + (int)check);
                break;
            }
            x++;
        }
    }

    if (ans.empty())
        cout << -1;

    else
        cout << *min_element(ans.begin(), ans.end());
}

　여기서 정수를 값이 정수인지, 실수인지 판별하기 위해 부동 소수점 개념을 이용하였다. 부동 소수점은 소수를 지수와 유효숫자로 표현하는 방법인데, 예를 들어 3.141592를 유효숫자와 지수료 표현하면 다음과 같다.

• 유효숫자: 3141592...
• 지수: 1

　따라서 항상 값을 근사치로 표현하기 때문에 정확한 값이 표현되지 않는다. 예를 들어보면 

#include <iostream> 
using namespace std;

int main()
{
	double d = 0.1;
	double d1(d+d+d+d+d+d+d+d+d);
	double d2(1);
		
	if(d1 == d2)
		cout << "TRUE" << endl;
	else
		cout << "FALSE" << endl;	
}

　다음과 같은 코드가 있을 때 출력은 TRUE일까 FALSE일까? 놀랍게도 답은 FALSE다. 값이 어떻게 표현되었는지 자세하게 파악하기 위해 자릿수를 늘려서 확인해보자.

#include <iostream> // 입출력 전처리문
#include <iomanip> // setprecision() 
using namespace std;

int main()
{
	double d = 0.1; // double d(0.1) 과 같음
	double d1(d+d+d+d+d+d+d+d+d);
	double d2(1);
		
	if(d1 == d2)
		cout << "TRUE" << endl;
	else
		cout << "FALSE" << endl;
	
	cout << setprecision(18) << endl;
	cout << d1 << endl << d2 << endl;
}

위의 코드 결과창

　

　이러한 개념을 이용해 -3x/5 + N/5를 실수형 변수로 check로 두고, check - (int)check를 했을 때 0이 된다면 정수고, 그렇지 않다면 실수인 것이므로 실수를 판별할 수 있다.