설탕 배달 2839

문제

접근 방법

5와 3을 가장 적게 사용하여 목표하는 수를 만드는 문제이다. 0부터 시작하여 5, 3으로 N을 안 넘게 이동하며 횟수를 기록하면 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int dx[] = {5, 3};
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N;
    cin >> N;
    vector<int> suger(N + 1);
    queue<int> bfs;
    bfs.push(0);
    while (!bfs.empty())
    {
        int cur = bfs.front();
        bfs.pop();
        if (cur == N)
            break;
        for (int i = 0; i < 2; ++i)
        {
            int next = cur + dx[i];
            if (next > N || suger[next])
                continue;
            suger[next] = suger[cur] + 1;
            bfs.push(next);
        }
    }
    if (suger[N])
        cout << suger[N];
    else
        cout << -1;
    return 0;
}

풀이

아직 방문하지 않은 곳을 방문하며 개수를 기록해주는 방식을 사용하였다.

DP 방식으로 N까지 돌아보는 방식도 있다. (3, 5만큼 떨어진 곳을 확인하는 방식)
5로 나누고 3으로 빼는 방식도 있었다. (이게 문제 의도에 가까운 풀이 같다)