[JAVA] 백준 알고리즘 14226번 문제풀이 (이모티콘)

ㅁ

 

 

 

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

14226번: 이모티콘

 

 

 

 

● 이모티콘 (14226번)

 

 

 

 

 

import java.util.*;
public class Quiz_14226 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] d = new int[n+1][n+1];
        for (int i=0; i<=n; i++) {
            Arrays.fill(d[i], -1);
        }
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        q.add(0);
        d[1][0] = 0;
        while (!q.isEmpty()) {
            int s = q.remove();
            int c = q.remove();
            if (d[s][s] == -1) {
                d[s][s] = d[s][c] + 1;
                q.add(s); q.add(s);
            }
            if (s+c <= n && d[s+c][c] == -1) {
                d[s+c][c] = d[s][c] + 1;
                q.add(s+c); q.add(c);
            }
            if (s-1 >= 0 && d[s-1][c] == -1) {
                d[s-1][c] = d[s][c] + 1;
                q.add(s-1); q.add(c);
            }
        }
        int ans = -1;
        for (int i=0; i<=n; i++) {
            if (d[n][i] != -1) {
                if (ans == -1 || ans > d[n][i]) {
                    ans = d[n][i];
                }
            }
        }
        System.out.println(ans);
    }
}

* 소스 풀이

​

우선 n을 통해 화면의 이모티콘 갯수를 입력받습니다.

그리고 d 이차원배열을 만들고 각각 -1로 초기화를 해줍니다.

-1을 저장하는 이유는 아직 방문하지않았기 때문입니다.

그리고 Queue를 만들어주고 scscsc 순으로 넣어주기위해 처음에 1,0을 add해줍니다.

while반복문을 통해 q가 없을때까지 반복하고, scscsc순으로 넣어주었기에 s,c를 순서대로 remove해줍니다.

여기서 s는 화면에의 이모티콘 개수이고, c는 클립보드에있는 이모티콘 개수입니다.

복사를 하기위해 만약 -1(방문하지않음)이면, 클립보드에있는 이모티콘을 모두 화면에 있는 이모티콘으로 바꿔줍니다.

sc순으로 위와동일하게 추가해줍니다.

붙여넣기와 삭제도 위와동일한 if문을 통해 만들어줍니다.

그리고 ans변수를 만들어서 i의 개수만큼 반복해주고 방문을 했다면, 최솟값을 계속 구해줘서

ans에 저장해주고 출력합니다.

 

 

< 백준알고리즘 강의를 보고 참고하였습니다! >

 

 

---