[백준 14226번] 이모티콘 - (Java/python)

문제 링크 : https://www.acmicpc.net/problem/14226

14226번: 이모티콘

 

Idea 

영선이가 할수 있는 일은 총 3가지가 있다. 

a. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장.

b. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기

c. 화면에 있는 이모티콘 하나 삭제

 

영선이가 하고자 하는 것은 이모티콘 s개를 만드는 것이다. 그리고 위 3가지 행위 모두 이 이모티콘 개수에 변화를 준다.

각 행위를 하는데 드는 시간은 1초로 동일 하다. 그리고 구하고자 하는 것은 이모티콘 s개를 만드는데 걸리는 최소 시간이다.

따라서 해당 문제 최단 거리를 구하는 문제와 같은 형태로 bfs로 풀수 있다. 

 

처음 생각한 방식은 미지수를 하나만 두고 해결하는 방식이였다. 

어짜피 중요한건 클립보드가 아닌 화면에 존재하는 이모티콘의 개수이니 화면에 있는 이모티콘만 생각하자는 것이였다.

그래프로 표현해 보면 대충 이런식으로 흐름을 볼수 있다. 

 

 

그런데 이런식으로 풀면 어떤 3가지중 하나의 행위를 했는데도 결과에 변화가 없다. 즉 행위를 하기 전과 똑같다. 

예를 들어 화면에 x개의 이모티콘이 있다고 하면 여기서 할수 일은 총 3가지(a,b,c) 이다.

그중에 a번을 수행하면 화면에 이모티콘 개수가 변하지 않고 똑같이 x가 나온다.

즉 클립보드에 값은 다르지만 화면에 있는 값이 동일한 경우가 나오는 것이다. 이렇게 되면 bfs로는 풀수가 없다.

 

 

다시 생각한 방법이 매개변수 2개를 사용하는 것이다.  화면에는 x개의 이모티콘이 있고, 클립보드에는 y개의 이모티콘이 있다고 가정하자.

그래프로 보면 다음과 같다. 

(x,y) -> (x,x)

(x,y) -> (x+y,y)

(x,y) ->(x-1,y)

위와 같이 3가지의 행위를 했을때 모든 정점의 값이 다 다른것을 볼 수 있다.

따라서 미지수 2개를 사용해서 코드를 작성하면 된다.

 

 

Java

public class Main {
    static final int MAX =  2000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt(); // 화면에 만들어야 될 이모티콘 개수
        int[][] dist = new int[MAX+1][MAX+1];
        Queue<Node> q = new LinkedList<>();

        for(int i=0; i<=MAX; i++){
            Arrays.fill(dist[i],-1);
        }
        Node start = new Node(1,0);
        q.add(start);
        dist[1][0] = 0;

        while(!q.isEmpty()){
            Node remove = q.remove();
            int x = remove.getScreen();
            int y = remove.getClip();

            if(dist[x][x]==-1){
                dist[x][x] = dist[x][y]+1;
                q.add(new Node(x,x));
            }

            if(y>0 && x+y<=MAX && dist[x+y][y]==-1){
                dist[x+y][y] = dist[x][y]+1;
                q.add(new Node(x+y,y));
            }

            if(x-1>=0 && dist[x-1][y]==-1){
                dist[x-1][y] = dist[x][y]+1;
                q.add(new Node(x-1,y));
            }

        }

        int ans = -1;
        for(int i=0; i<=s; i++){
            if(dist[s][i]!=-1){
                if(ans==-1 || ans>dist[s][i]){
                    ans = dist[s][i];
                }
            }
        }

        System.out.println(ans);

    }

}

class Node{
    private int screen;
    private int clip;

    public Node(int screen,int clip){
        this.screen = screen;
        this.clip = clip;
    }

    public int getScreen() {
        return screen;
    }

    public void setScreen(int screen) {
        this.screen = screen;
    }

    public int getClip() {
        return clip;
    }

    public void setClip(int clip) {
        this.clip = clip;
    }
}

 

MAX를 2000으로 둔 이유는 입력값이 최대 1000인데 

예를들어 (700,700)인 경우에서 b. 를 수행하면 (1400,700) 이 되므로 1000을 넘는다. 따라서 최대 2000으로 잡아주었다.

 

또한 Java의 경우 화면에 있는 이모티콘 개수와 클립보드에 있는 이모티콘 개수를 둘다 저장하기 위해 Node라는 클래스를 만들어 큐에 저장하는 방식을 사용했다.

 

 

Python

from collections import deque

MAX = 2000
n = int(input())
dist = [[-1]*(MAX+1) for _ in range(MAX+1)]

q = deque()

q.append((1,0))
dist[1][0] = 0


while q:
    s,c = q.popleft()

    if dist[s][s] == -1:
        dist[s][s] = dist[s][c]+1
        q.append((s,s))

    if s+c<=MAX and dist[s+c][s]== -1:
        dist[s+c][c] = dist[s][c] +1
        q.append((s+c,c))

    if s-1>=0 and dist[s-1][c]== -1:
        dist[s-1][c] = dist[s][c] +1
        q.append((s-1,c))


ans = -1
for i in range(MAX+1):
    if dist[n][i] !=-1:
        if ans == -1 or ans>dist[n][i]:
            ans = dist[n][i]

print(ans)

 

**파이썬은 python3 로 풀면 시간 초과가 발생하므로 pypy3로 돌려주었다.**