글 읽기 - 더럽게 만들었지만 작동은 됩니다 어떤 예외사항이 있을까요?

bbagwang 7년 전 0

한동안 쉬다가 오랜만에 와서 다시 해보려는데

이전에 어떤분이 답글 달아주신걸 최근에 보고 깨달음을 얻어

다시 코드를 짜보았습니다만 제 기준에선 예외사항이 없이 잘 작동 하는 것 같으나

체점에서 틀렸다고 나옵니다 ㅠㅠ

한번 둘러봐 주시면 감사하겠습니다.

#include <iostream>
using namespace std;

int main()
{
	int bag_3kg=0;
	int bag_5kg=0;
	int temp=0;
	int total_bag=0;
	int base;

	cin >> base;

	//5KG Priority after 3KG
	for (temp; temp <= base;)
	{
		temp += 5;
		++bag_5kg;

		if (temp == base)
		{
			cout << bag_5kg << endl;
			return 0;
		}
		else if (temp > base&&temp != base)
		{
			temp -= 5;
			bag_5kg--;
			break;
		}
	}
	for (temp; temp <= base;)
	{
		temp += 3;
		++bag_3kg;

		if (temp == base)
		{
			total_bag = bag_3kg + bag_5kg;
			cout << total_bag << endl;
			return 0;
		}
		else if (temp > base&&temp != base)
		{
			bag_3kg = bag_5kg = temp = 0;
			break;
		}
		else
		{
			continue;
		}
	}

	//3KG Priority
	for (temp; temp <= base; )
	{
		temp += 3;
		++bag_3kg;
		if (temp == base)
		{
			cout << bag_3kg << endl;
			return 0;
		}
		else if (temp > base&&temp != base)
		{
			bag_3kg = temp = 0;
			break;
		}
		else
		{
			continue;
		}
	}

	//8KG Priority (3KG+5KG)
	for (temp; temp <= base;)
	{
		temp += 8;
		++bag_3kg;
		++bag_5kg;

		if (temp == base)
		{
			total_bag = bag_3kg + bag_5kg;
			cout << total_bag << endl;
			return 0;
		}
		else if(temp>base&&temp!=base)
		{
			cout << "-1" << endl;
			return 0;
		}
		else
		{
			continue;
		}
	}
}

simm4256 7년 전 2

자연수 n이 주어졌을 때

n = a*3 + b*5

로 나타낼 수 있으면

a+b의 최솟값을 출력하는 문제입니다.

그럼 a+b의 최솟값은 어떻게 구할 수 있을까요?

n = 30 일 때를 생각해봅시다.

이 때 가능한 a,b 쌍은 3개가 있습니다.

a=10, b=0 ==> a+b=10

a=5, b=3 ==> a+b=8

a=0, b=6 ==> a+b=6

눈치채셨나요?

a가 작을수록 a+b의 값이 작아집니다.

어찌보면 당연한 얘기죠. 3kg 봉지를 적게 써야 5kg 봉지를 많이 쓸태니까요.

자연수 n이 32입니다. a+b의 최솟값은 어떻게 구하면 될까요?

a,b 쌍이 여러 개 나올탠데

그 중 a가 가장 작은 방법을 찾으면 되겠죠?

a=4, b=4, a+b=8

이 방법이 최소가 되겠네요.

이걸 일반화하시면 말도 안되게 쉬운 알고리즘이 나옵니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

더럽게 만들었지만 작동은 됩니다 어떤 예외사항이 있을까요?

bbagwang 7년 전 0

simm4256 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말