2839번 설탕 배달

나는 2가지 풀이 방법으로 풀었다.

1. 무식하게 구현(완전 탐색, 브루트 포스)

2. BFS

https://www.acmicpc.net/problem/2839

<무식하게 찾아내기(완전 탐색, 브루트 포스)>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int main(void)
{
    int N = 0;
 
    scanf("%d", &N);
 
    int sum = 987654321;
 
    for (int x = 0; x <= N; x++)
    {
        for (int y = 0; y <= N; y++)
        {
            if (5 * x + 3 * y > N) continue;
 
            if (5 * x + 3 * y == N)
            {
                sum = min(sum, x + y);
            }
        }
    }
    
    if (sum == 987654321) printf("-1\n");
    else printf("%d\n", sum);
 
    return 0;
}

<BFS>

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int BFS(int start)
{
    queue<int> q;
 
    bool visit[5001] = { false, };
 
    memset(visit, false, sizeof(visit));
 
    q.push(start);
 
    visit[start] = true;
 
    int ret = 0;
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int weight = q.front();
 
            q.pop();
 
            if (weight == 0) return ret;
 
            if (weight - 5 >= 0 && !visit[weight - 5])
            {
                q.push(weight - 5);
                visit[weight - 5] = true;
            }
 
            if (weight - 3 >= 0 && !visit[weight - 3])
            {
                q.push(weight - 3);
                visit[weight - 3] = true;
            }
        }
 
        ++ret;
    }
 
    return -1;
}
 
int main(void)
{
    int N = 0;
 
    scanf("%d", &N);
 
    printf("%d\n", BFS(N));
 
    return 0;
}