[백준] 알고리즘 14226번 - 이모티콘문제

문제

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

14226번: 이모티콘

소스코드

#include <iostream>
#include <limits.h>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int dist[2001][2001];
int n;
queue<pair<int, int>> qu;

void bfs(int x, int y) {
	qu.push({ x,y });
	while (!qu.empty()) {
		int ox = qu.front().first;
		int oy = qu.front().second;
		qu.pop();
		if (dist[ox][ox] == 0) {
			qu.push({ ox,ox });
			dist[ox][ox] = dist[ox][oy] + 1;
		}
		if (dist[ox + oy][oy] == 0 && ox + oy <= n) {
			qu.push({ ox + oy,oy });
			dist[ox + oy][oy] = dist[ox][oy] + 1;
		}
		if (dist[ox - 1][oy] == 0 && ox-1>=2) {
			qu.push({ ox - 1,oy });
			dist[ox - 1][oy] = dist[ox][oy] + 1;
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> n;
	bfs(1, 0);
	int ans=INT_MAX;
	for (int i = 0; i <= n; i++) {
		if (dist[n][i] != 0) {
			ans = min(ans, dist[n][i]);
		}
	}
	cout << ans;
}

해설

 

문제의 요지는 현재의 스크린과 클립보드의 상태에 따라서 나올 수 있는 결과가 다 다르다는 점이다.

또한 각각의 조건은 1초가 걸린다고하니, 가중치가 1인셈이다. 그렇다면 bfs로 거리에따라 1초식 더해주면된다.