[BAEKJOON 2839번 : 설탕 배달]
[문제]
[고찰]
해당 문제에 대해 저는 아래와 같이 풀었습니다.
저는 5를 우선적으로 빼는 조건을 3의 배수가 아니거나 n이 10보다 클 때로 정했습니다.
그리고 위의 조건을 만족하지 않으면 3을 빼게 하였습니다.
조건을 이렇게 정한 이유는, n이 3의 배수가 아니면 당연히 5를 빼면 되고, n이 10보다 커야한다는 조건은 n이 18일 때 3의 배수이지만 5로 우선적으로 빼야하기 때문입니다. 그래서 10보다 큰 n에 대해서는 우선적으로 5를 빼게 설정한 것이였습니다.
하지만, 이 문제 풀이는 잘못된 풀이였습니다.
n이 12일 때를 생각해보면, n은 10보다 크기 때문에 5를 우선적으로 빼게됩니다.
하지만 5를 뺀 후의 7이 된 n은 어떻게 해도 원하는 답으로 도출되지 못합니다.
제대로된 정답은 n을 모두 3으로 빼는 것이기 때문입니다.
이런 식으로 제가 설정한 조건은 너무 애매한 조건이였습니다.
이에 제대로 된 방법을 정리하고자 합니다.
아래의 코드는 제가 작성한 틀린 답변입니다.
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int count = 0;
while (1)
{
if (n == 0)
{
break;
}
else if (n < 0)
{
count = -1;
break;
}
if ((n % 3) != 0 || n > 10)
{
n -= 5;
count++;
}
else
{
n -= 3;
count++;
}
}
cout << count;
return 0;
}[개념]
처음에 5를 빼는 조건을, n이 3의 배수가 아닐 때를 기준으로 잡는 것이 아니라 단순히 n을 5로 나눴을 때 나머지가 0이라는 것으로 기준을 잡았으면 됐었습니다.
그리고 위의 조건이 아닐 때는 3을 빼면 되는 것입니다.
예를 들어 n이 18이라면, 5의 배수가 아니기 때문에 3을 뺍니다.
이후의 n은 15가 되기 때문에 5의 배수라는 조건을 충족하게 됩니다.
n이 5의 배수라는 조건을 충족하게 되면, 3을 고려하지 않아도 되기 때문에 더 이상 n에 추가적인 계산을 하지 않고, count를 n / 5만큼 더해주면 됩니다.
이를 코드로 구현하면 아래와 같습니다.
while (1)
{
if (n % 5 == 0)
{
count += n / 5;
break;
}
n -= 3;
count++;
if (n < 0)
{
count = -1;
break;
}
}
만약 위의 방식이 아니라, n % 3 == 0일 때, count += n / 3;을 하고,
아래에서는 n −= 5를 한다고 하면 최소 봉지 수를 보장하지 않는다는 문제가 발생합니다.
그렇기 때문에 n에서 3을 빼면서, n을 5의 배수로 만드는 방식이 옳은 풀이입니다.
[정리]
위의 정리한 것과 같이 계산하면 되는 문제인데, 저는 큰 수인 5로부터 우선적으로 뺄 생각을 하느라 시야가 좁아졌던 것 같습니다.
시야를 넓혀야 하는데 문제를 풀다보면 계속해서 좁아지고, 어떻게든 예제 입력 답변에 맞추기 위해 억지로 조건을 껴맞치고 있습니다.
계속 놓치고 있는 부분들을 계속 생각하면서 발전해 나가도록 하겠습니다.
[Solution]
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int count = 0;
while (1)
{
cout << n << endl;
if (n % 5 == 0)
{
count += n / 5;
break;
}
n -= 3;
count++;
if (n < 0)
{
count = -1;
break;
}
}
cout << count;
return 0;
}