문제

BOJ 14226: 이모티콘 https://www.acmicpc.net/problem/14226

풀이

조건

• 다음과 같은 3가지 연산만 사용한다.
  1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
  2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
  3. 화면에 있는 이모티콘 중 하나를 삭제한다.
• 모든 연산은 1초가 걸린다.
• 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다.
• 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없다.
• 일부만 클립보드에 복사할 수는 없다.
• 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다.
• 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.

풀이 순서

• 최소 시간을 구해야 하므로 BFS를 사용한다.
• 조건에 맞게 1, 2, 3번 연산을 수행하고 현재 화면에 있는 이모티콘의 갯수가 S와 같으면 종료한다.
• 방문 처리를 해주어 같은 구간 반복을 방지한다.
  • isVisited[클립 보드에 있는 갯수][화면에 보여지는 갯수]
• Queue에 담길 때마다 time + 1 을 해준다.

코드

import java.util.*;
import java.io.*;

public class Main {
    
	static int S;
	static boolean[][] isVisited = new boolean[1001][1001]; // [clipboard][total]
	
    public static void main(String[] args) throws IOException {
    	Scanner sc = new Scanner(System.in);
    	
    	S = sc.nextInt();
    	sc.close();
    	
    	bfs(S);
	
    }
    
    static void bfs(int target){
    	Queue<Imo> que = new LinkedList<>();
    	
    	que.add(new Imo(0, 1, 0));
    	isVisited[0][1] = true;
    	
    	while(!que.isEmpty()) {
    		Imo now = que.poll();
    		
    		if(now.total == target) {
    			System.out.println(now.time);
    			return;
    		}
    		
    		// 클립 보드에 저장
    		// 화면에 있던 이모티콘을 전부 클립 보드에 복사해 넣음
    		que.add(new Imo(now.total, now.total, now.time + 1));
    		
    		// 클립 보드에 있는 이모티콘을 화면에 붙여넣기
    		// 클립 보드가 비어있지 않고 && 화면에 붙여넣은 후 개수가 총 개수보다 적어야 하고 && 아직 방문 안함
    		if(now.clipboard != 0 && now.total + now.clipboard <= target && !isVisited[now.clipboard][now.total + now.clipboard]) {
    			que.add(new Imo(now.clipboard, now.clipboard + now.total, now.time + 1));
    			isVisited[now.clipboard][now.total + now.clipboard] = true;
    		}
    		
    		// 화면에서 이모티콘 하나 삭제
    		// 총 개수가 1 이상이고 && 아직 방문 안함
    		if(now.total >= 1 && !isVisited[now.clipboard][now.total - 1]) {
    			que.add(new Imo(now.clipboard, now.total - 1, now.time + 1));
    			isVisited[now.clipboard][now.total - 1] =  true;
    		}
    	}
    }
    
    static class Imo{
	   int clipboard;
	   int total;
	   int time;
	   
	   Imo(int clipboard, int total, int time){
		   this.clipboard = clipboard;
		   this.total = total;
		   this.time = time;
	   }
    }
}

정리

• 문제 이해가 잘 되지 않아서 시간 낭비를 했다.