[백준] 14226 이모티콘

1. 문제

www.acmicpc.net/problem/14226%EF%BB%BF

14226번: 이모티콘

2. 접근방법

최단으로 지정된 숫자에 도달하는 것이니

bfs를 사용해서 모든 경우의수로 이동해보면서 해당하는 숫자에 도달했을때 depth를 구했다.

visit처리를 2차원배열로 해서 현재개수와 클립보드에 저장된 갯수 두가지로 체크하면서 이동했다.

 

처음에 dp로 풀어야 하나? 했는데 N이 작아서 그냥 bfs로 풀었는데 풀리더라.

dp로 풀면 속도 좀 더 줄긴 하겠징

3. 자바 코드

package Gold;

import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class P14226이모티콘 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		boolean visit[][] = new boolean[10001][10001];

		Queue<Point> que = new LinkedList<Point>();
		que.offer(new Point(1, 0)); // x= 현재 개수 y = 클립보드 개수
		visit[1][0] = true;
		int cnt = 0;
		gg:while (!que.isEmpty()) {
			int size = que.size();
			for (int i = 0; i < size; i++) {
				Point now = que.poll();
				if(now.x == N) {
					break gg;
				}
				if (!visit[now.x][now.x]) {
					visit[now.x][now.x] = true;
					que.offer(new Point(now.x, now.x));
				}
				if(now.x-1 >0 && !visit[now.x-1][now.y]) {
					visit[now.x-1][now.y] = true;
					que.offer(new Point(now.x-1,now.y));
				}
				if(!visit[now.x+now.y][now.y]) {
					visit[now.x+now.y][now.y] = true;
					que.offer(new Point(now.x+now.y, now.y));
				}
			}
			cnt++;
		}
		System.out.println(cnt);
	}

}

4. 마치며

시간제한이 2초라 그냥 bfs로도 풀렸다. N이 좀만 커지거나 시간 줄어들면 dp로 풀어야 할 것이다.