[BOJ 28069 // C++] 김밥천국의 계단

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

 

이번에 볼 문제는 백준 28069번 문제인 김밥천국의 계단이다.
문제는 아래 링크를 확인하자.

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

28069번: 김밥천국의 계단

0번 계단에서 각 n번째 계단까지 올라가는 데에 x번 계단 오르기로 올라갈 수 있다면 x보다 큰 횟수 y로도 올라갈 수 있음을 관찰하자. 이는 0번 계단에서 2번 행동을 x와 y의 차만큼 반복하고 x번 계단 오르기를 하는 것으로 가능하다.

 

위의 관찰을 이용하면 N번 계단까지 필요한 최소 계단 오르기 횟수를 구해 그 값이 K보다 작거나 같은지를 판단하는 것으로 문제를 해결할 수 있다. 최소 계단 오르기 횟수는 각 계단을 노드로, 각 계단에서 이동할 수 있는 계단의 관계를 방향 에지로 갖는 그래프 모델링에서의 BFS를 이용해 구할 수 있다.

 

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

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

int N, K;
int dist[1000001];

queue<int> que;
void bfs() {
	dist[0] = 1;
	que.push(0);
	while (!que.empty()) {
		int cur = que.front(); que.pop();
		int nxt1 = cur + 1, nxt2 = cur + cur / 2;
		if (nxt1 <= 1000001 && !dist[nxt1]) {
			dist[nxt1] = dist[cur] + 1;
			que.push(nxt1);
		}
		if (nxt2 <= 1000001 && !dist[nxt2]) {
			dist[nxt2] = dist[cur] + 1;
			que.push(nxt2);
		}
	}
}

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

	bfs();

	cin >> N >> K;

	if (dist[N] - 1 <= K) cout << "minigimbob";
	else cout << "water";
}