취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 13910번 문제인 개업이다.
문제는 아래 링크를 확인하자.

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

문제의 상황을 그래프로 모델링해보자. 먼저, k인분을 만든 상황을 노드 k라 하자. 그리고 현재 p인분의 요리를 만들었을 때 한번의 추가 조리를 거쳐 총 q인분을 완성시킬 수 있는 관계를 노드p에서 q로 향하는 에지로 나타내자. 이 때, 주어진 문제는 노드0에서 노드N까지의 최단거리를 구하는 문제로 생각할 수 있다. 이는 BFS를 이용해 간단히 구해낼 수 있다.

요리는 한번에 한 개의 웍 또는 두 개의 웍으로 진행할 수 있으므로, 한 번의 요리에 만들 수 있는 요리의 양을 먼저 전처리해두자.

아래는 제출한 소스코드이다.

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

int N, M;
int onedish[100];
bool dishes[10001];
vector<int> vec;

int dist[10001];

void bfs() {
	dist[0] = 1;
	queue<int> que;
	que.push(0);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& x : vec) {
			int nxt = cur + x;
			if (nxt > N || dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) cin >> onedish[i];
	for (int i = 0; i < M; i++) {
		dishes[onedish[i]] = 1;
		for (int j = i + 1; j < M; j++) {
			int tmp = onedish[i] + onedish[j];
			if (tmp <= N) dishes[tmp] = 1;
		}
	}

	for (int i = 1; i <= N; i++) {
		if (dishes[i]) vec.emplace_back(i);
	}

	bfs();

	cout << dist[N] - 1;
}