[백준] 14226, 이모티콘 Java

14226, 이모티콘

x2 와 -1 로 주어진 숫자를 만들면 되는, 어디서 많이 본 듯한 문제다.

다른 문제들과 다른 점은 복사, 붙여넣기 기능이 추가로 있는 차이점이 있다.

만들어야하는 숫자는 최대 1000 이므로 완전 탐색을 해도 충분히 커버 가능할 것 같다

이용할 수 있는 방법의 가짓수는 아래 3가지이다.

1. 복사
2. 붙여넣기
3. -1

이모티콘 1개에서 시작하여 시간이 증가할 때 마다 3가지 방법을 모두 고려해주면 된다.

이 때, dfs 혹은 bfs를 사용해 탐색이 가능한데 dfs를 쓰는 방법은 시간초과가 날 가능성이 있다 (실제로 발생한다).

왜냐하면 정말 모든 경우를 다 탐색하기 때문에 대략 3^s 만큼의 시간이 소요된다. 아마도 dfs를 사용하기 위해선 dp를 함께 사용해야 할 것 같다는 생각이 든다.

따라서 brute force 방법으로 이 문제를 해결하려면 최소의 시간을 찾아내면 바로 종료할 수 있는 bfs를 사용해야한다.

이 때, 이미 방문했던 숫자를 다시 방문하지 않기위해 (무한 루프를 돌지않기위해) visit 배열을 만들어야한다.

주의 해야할 점은 숫자 n을 방문할 때, clipBoard에 어떤 값이 있냐에 따라 발생할 수 있는 결과값이 다르다는 점이다.

만약, n을 방문할 때 clipBoard에 1이 있다면 다음 결과물이 n+1이 될 수 있지만 만약 2가 있다면 결과물은 n+2 다.

따라서 visit 을 검사할 때 clipBoard도 함께 고려해 줘야한다.

전체 코드

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


public class Main{
    static int s;
    static boolean visit[][];
    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());
        visit = new boolean[3*s][3*s];
        Queue<emo> emos = new LinkedList<emo>();
        visit[1][0]=true;
        emos.add(new emo(0,1,0));
        while(emos.size()!=0){
            emo polled = emos.poll();
            if(polled.num==s){
                System.out.println(polled.cnt);
                break;
            }
            if(!visit[polled.num][polled.num]){
                visit[polled.num][polled.num]= true;
                emos.add(new emo(polled.cnt+1,polled.num,polled.num));
            }
            if(!visit[polled.num-1][polled.clip]&&polled.num!=1){
                visit[polled.num-1][polled.clip]=true;
                emos.add(new emo(polled.cnt+1,polled.num-1,polled.clip));
            }
            if(polled.clip!=0 && !visit[polled.num+polled.clip][polled.clip] && polled.num+polled.clip<=s){
                visit[polled.num+polled.clip][polled.clip] = true;
                emos.add(new emo(polled.cnt+1,polled.num+polled.clip,polled.clip));//붙여넣기
            }
        }        

        
    }
}

class emo{
    int cnt;
    int num;
    int clip;
    public emo(int cnt,int num,int clip){
        this.cnt = cnt;
        this.num = num;
        this.clip = clip;
    }
}