Boj16568_엔비스카의 영혼

Published: December 04, 2018 by 아형

• Categories:
• Algorithm 74

• Tags:
• 알고리즘 72

백준 16568 엔비스카의 영혼

• 문제를 꼼꼼히 잘 읽자! 그냥 For 문으로도 문제 해결 가능.
• 더 좋은 코드 : https://www.acmicpc.net/source/10920143

#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,a,b;

struct node {
	
	int cnt;//시간
	int idx;//위치
};
int visit[1000001];
queue<node> q;
int min_time=1e9;
int main() {
	scanf("%d %d %d", &n, &a, &b);
	q.push(node{ 0, n+1 });
	while (!q.empty()) {
		node nownode = q.front();
		q.pop();
		if (nownode.idx == 1) {
			min_time = min(min_time, nownode.cnt);
		}
		else {
			nownode.idx--;
			if (nownode.idx >= 0 && !visit[nownode.idx]) { q.push(node{ nownode.cnt + 1, nownode.idx }); visit[nownode.idx] = 1; }
			if (nownode.idx - a >= 0 && !visit[nownode.idx - a]) { q.push(node{ nownode.cnt + 1, nownode.idx - a }); visit[nownode.idx - a] = 1; }
			if (nownode.idx - b >= 0 && !visit[nownode.idx - b]) { q.push(node{ nownode.cnt + 1, nownode.idx - b }); visit[nownode.idx - b] = 1; }

		}
	}
	printf("%d", min_time);
}