취미로 코딩하기

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

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

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

이 문제는 13910번 문제(링크)에서 웍의 개수 M의 제한을 1000으로 늘린 문제이다. 이로 인해 딱히 문제 풀이가 달라지거나 하지는 않으므로 해당 문제의 풀이글을 참고해 문제를 해결하자.

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

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

int N, M;
int onedish[1000];
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;
}