[BOJ 14226] 이모티콘(Java, 간단한 코드, 런타임에러, 증명)

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

14226번: 이모티콘

 

 

이 문제를 Bottom-up으로 접근할 수 없다. 화면에 있는 이모티콘 중 하나를 삭제하기 때문에, 순차적인 접근이 이루어지기 어렵다.

 

 

 

 

1. Top-Down 방식으로 DP를 작성한다. DP의 매개변수는, 화면에 이모티콘 수와 클립보드 이모티콘 수로 2개를 사용한다.

 

 

 

 

2. BFS를 이용해서, 3가지 기능에 대해서 구현해주면 된다. 또한, 메모이제이션 기법을 통해서 중복을 제거해 시간복잡도를 줄이도록 한다.

* 런타임에러가 발생하는 경우, 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 할 때 인덱스 범위를 확인하도록 한다.

 

 

 

 

 

 

해설코드(Java).

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    static class Item{
        int E, C, depth;
        Item(int E, int C, int depth){
            this.E = E;
            this.C = C;
            this.depth = depth;
        }
    }
    
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int S = Integer.valueOf(br.readLine());
        boolean[][] dp = new boolean[1001][1001];
        int depth = 1;
        
        Queue<Item> q = new LinkedList<>();
        q.offer(new Item(1, 1, 1));
        dp[1][1] = true;
        
        while(!q.isEmpty()){
            Item i = q.peek();
            
            if(i.E == S){
                bw.write(i.depth + "\n");
                break;
            }
            
            if(i.E - 1 != 0 && dp[i.E - 1][i.C] == false){
                q.offer(new Item(i.E - 1, i.C, i.depth + 1));
                dp[i.E - 1][i.C] = true;
            }
            
            if(dp[i.E][i.E] == false){
                q.offer(new Item(i.E, i.E, i.depth + 1));
                dp[i.E][i.E] = true;
            }
            
            if(i.E + i.C <= S && dp[i.E + i.C][i.C] == false){
                q.offer(new Item(i.E + i.C, i.C, i.depth + 1));
                dp[i.E + i.C][i.C] = true;
            }
            
            q.poll();
        }
        
        bw.flush();
    }
}