[백준 14226번 / java] 이모티콘

문제

14226번: 이모티콘 (acmicpc.net)

1. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
3. 화면에 있는 이모티콘 중 하나를 삭제한다.

풀이

첫 시도

복붙 : 약수 x를 찾아 dp[S] = min(dp[x1] + S/x1, dp[x2] + S/x2, ...)를 수행

삭제 : 복붙이 모두 완료된 dp에서 모든 수 i에 대해 j기준 역순으로 dp[i]와 dp[j]+(삭제하는 시간)을 비교해 삭제가 더 빠른지 확인 dp[i] = min(dp[i], dp[j]+(j-i))

 

테케와 질문게시판의 반례는 맞았지만 오답처리됨

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

public class Main {
    static int S;
    static int[] dp;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        S = Integer.parseInt(br.readLine());

        dp = new int[1001];

        dp[1] = 0;
        dp[2] = 2;
        dp[3] = 3;

        if(S > 3){
            for(int i=4; i<=S; i++){
                dp1(i);
                dp2(i);
            }
        }

        bw.write(dp[S] + " ");
        bw.close();

    }
    static void dp1(int N){ //복사 붙여넣기
        List<Integer> divisors = new ArrayList<>();
        for(int i=1; i<N; i++){
            if(N%i == 0){ //약수 찾기
                divisors.add(dp[i]+N/i);
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i=0; i<divisors.size(); i++){
            if(min > divisors.get(i))
                min = divisors.get(i);
        }
        dp[N] = min;
    }
    static void dp2(int N){ //삭제
        for(int i=1; i<=N; i++){
            for(int j=N; j>=i; j--){
                dp[i] = Math.min(dp[i], dp[j]+(j-i));
            }
        }
    }
}

해결 방법

복붙 -> 약수만 고려하는 방법은 잘못된 방법

bfs로 모든 (입력된 갯수, 클립보드에 저장된 갯수)순서쌍을 순회한다.

time+1되는 경우마다 가지치기해서 모든 경우를 고려해야 함

 

visited배열을 visited[cur][clipboard]로 정의하는 이유는 모든 상태를 관리하기 위해서이다.

(cur, clipboard) = (5, 2) 상태와 (5, 3) 상태는 화면에 동일하게 5개의 이모티콘이 있어도 클립보드에 저장된 이모티콘이 다르기 때문에 서로 다른 상태로 간주

코드

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

public class Main {
    static Queue<Node> q = new LinkedList<>();
    static boolean[][] visited = new boolean[2000][2000];
    static int S;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        S = Integer.parseInt(br.readLine());

        bfs(new Node(1, 0, 0));

    }
    static void bfs(Node node){

        q.add(node);
        visited[node.cur][node.clipboard] = true;

        while(!q.isEmpty()){
            Node now = q.poll();

            //복사
            if(!visited[now.cur][now.cur]){
                visited[now.cur][now.cur] = true;
                q.offer(new Node(now.cur, now.cur, now.time+1));
            }

            //붙여넣기
            if(now.clipboard+now.cur == S){
                System.out.println(now.time+1);
                return;
            }
            if(now.cur+now.clipboard<=1000 && !visited[now.cur+now.clipboard][now.clipboard]){
                visited[now.cur+now.clipboard][now.clipboard] = true;
                q.offer(new Node(now.cur+now.clipboard, now.clipboard, now.time+1));
            }

            //삭제
            if(now.cur-1 == S){
                System.out.println(now.time+1);
                return;
            }
            if(now.cur-1>=0 && !visited[now.cur-1][now.clipboard]){
                visited[now.cur-1][now.clipboard] = true;
                q.offer(new Node(now.cur-1, now.clipboard, now.time+1));
            }
        }
    }
}
class Node{
    int cur, clipboard, time;
    Node(int cur, int clipboard, int time){
        this.cur = cur;
        this.clipboard = clipboard;
        this.time = time;
    }
}

Note

• 인기 있는 문제인가보다 오전부터 채점현황이 많이 업데이트된다.
• 방문체크하는 부분을 어떻게 정의해야 하는지 감이 잡히지 않아서 어려웠다.