https://www.acmicpc.net/problem/14226
14226번: 이모티콘
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만
www.acmicpc.net
문제
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.
영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
조건
첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.
문제풀이
간만에 정말 오래간만에 풀이 방법을 찾아보지 않고 혼자서 푼 문제이다
최근에는 풀다가 결국 못풀어서 포기하고 해설과 코드를 찾아보면서 '나는 아무래도 개발자랑은 안맞나..?' 이런 생각을 하곤 했는데 이번에는 그래도 풀 수 있었다.
이번 이모티콘 문제는 지난번 숨바꼭질 문제와 거의 동일하다.
문제를 이해하는데 살짝...? 어려울 수도 있지만 그것만 빼면 사실 거의 동일하다고 생각한다.
아래의 3가지를 주의하면서 풀자!
1. 코드에서의 view 는 화면, list 는 클립보드, viewAndList 배열은 방문을 체크하는 체크 배열이다. 즉 view 가 2 이고, list 가 3일 때 viewAndList[2][3] = true 가 되고 추후 view = 2, list = 3 는 더이상 방문하지 않는다.
2. 조건 1, 2, 3 을 정리하면 결국 아래와 같다.
- 복사 1) 복사할때는 view의 갯수가 그대로 list 의 갯수가 된다 => view 와 list 의 값은 일치 ->> view = list -> viewAndList[view][view] = true
- 붙여넣기 2) 붙여넣기 할 때는 view 에 list 의 값을 더한다 => view = view+list -> viewAndList[view+list][list] = true
- 삭제 3) 삭제 시에는 view 에서 이모티콘 1개 삭제한다 => view = view -1 -> viewAndList[view-1][list] = true
3. 각각의 조건에서 최대값과 최소값을 계산해주어야한다. 최대 이모티콘 갯수는 1000개임으로 view+list 했을 때 1000보다 작거나 같아야하며, 최소 0 개 임으로 view 는 0보다 크거나 같아야한다. view 가 -1 이 될 수는 없다!!
나머지는 주석 참고!
고백하자면 아래 코드는 정답을 맞춘 후 다른 사람들의 풀이를 보고 살짝 수정한 코드이다ㅠㅠ
package baekJoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
// view 는 현재 화면에 표시되는 이모티콘의 갯수
// list 는 클립보드에 저장된 이모티콘의 갯수
public class Quiz_14226_풀이완료 {
// https://www.acmicpc.net/problem/14226
static int n;
// viewAndList 는 각각의 인덱스 번호가 view 의 이모티콘 갯수, list 의 이모티콘 갯수이다.
// 예를 들어 viewAndList[1][2] 라면 view 의 이모티콘 갯수는 1, list 의 이모티콘 갯수는 2 를 의미한다
// 해당 배열은 BFS 가 돌면서 view 와 list 가 똑같은 값을 방문하지 않도록 하기 위한 배열이다.
static boolean[][] viewAndList = new boolean[1001][1001];
// queue 에는 Emoticon 클래스 객체를 넣는다.
// Emoticon 클래스에는 현재 view 이모티콘 갯수, list 이모티콘 갯수, 시간(time) 의 값이 들어간다
static Queue<Emoticon> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
// 처음에 있는 view 의 이모티콘 갯수는 0, 클립보드도 0, 시간도 0 초!
q.offer(new Emoticon(1, 0, 0));
System.out.println(makeEmo());
}
static int makeEmo() {
while (!q.isEmpty()) {
Emoticon e = q.poll();
int view = e.view;
int list = e.list;
int time = e.time;
// view 에 있는 이모티콘의 갯수가 n 과 동일하다면 끝!
if (view == n) {
return time;
} else {
// 복사 : 복사는 view 와 list 가 동일한 값이 된다 => view = list
if (!viewAndList[view][view]) {
viewAndList[view][view] = true;
q.offer(new Emoticon(view, view, time + 1));
}
// 붙여넣기 : 붙여넣기는 현재 view 에서 클립보드(list) 에 있는 이모티콘 갯수를 추가한다
// view = view + list
if (view + list <= 1000 && !viewAndList[view + list][list]) {
viewAndList[view + list][list] = true;
q.offer(new Emoticon(view+list, list, time + 1));
}
// 삭제 : 삭제는 현재 view 에서 -1 했을 때 0 과 같거나 0보다 큰 값이 나와야한다.
if (view - 1 >= 0 && !viewAndList[view - 1][list]) {
viewAndList[view - 1][list] = true;
q.offer(new Emoticon(view - 1, list, time + 1));
}
}
}
return -1;
}
}
class Emoticon {
int view;
int list;
int time;
Emoticon(int view, int list, int time) {
this.view = view;
this.list = list;
this.time = time;
}
}
참고로 이건 원래 코드!!
원래 코드는 viewAndList 대신 각각 따로 배열을 생성해서 관리했으며, 이 때문에 for 문이 따로 돌면서 방문을 체크한다.
보면 알겠지만...훨씬 복잡하고, 코드도 길다. 아직 갈길이 멀다ㅠㅠ
mport java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
// https://www.acmicpc.net/problem/14226
static int n;
static boolean[] viewChk = new boolean[1001];
static boolean[] listChk = new boolean[1001];
static Queue<Emoticon> q = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
q.offer(new Emoticon(1, 0, 0));
System.out.println(makeEmo());
}
static int makeEmo() {
while (!q.isEmpty()) {
Emoticon e = q.poll();
int view = e.view;
int list = e.list;
int time = e.time;
if (view == n) {
return time;
} else {
for (int i = 0; i < 3; i++) {
int nowView = view;
int nowList = list;
switch (i) {
case 0: // 복사
nowList = nowView;
if (!viewChk[nowView] || !listChk[nowList]) {
viewChk[nowView] = true;
listChk[nowList] = true;
q.offer(new Emoticon(nowView, nowList, time + 1));
}
break;
case 1: // 붙여넣기
nowView += nowList;
if (nowView <= 1000 && nowList != 0) {
viewChk[nowView] = true;
listChk[nowList] = true;
q.offer(new Emoticon(nowView, nowList, time + 1));
}
break;
case 2: // 삭제
nowView -= 1;
if (nowView >= 0) {
viewChk[nowView] = true;
listChk[nowList] = true;
q.offer(new Emoticon(nowView, nowList, time + 1));
}
}
}
}
}
return -1;
}
}
class Emoticon {
int view;
int list;
int time;
Emoticon(int view, int list, int time) {
this.view = view;
this.list = list;
this.time = time;
}
}
'Java - 알고리즘' 카테고리의 다른 글
| 백준 - 10825 국영수 (0) | 2022.08.18 |
|---|---|
| 백준 - 7568 덩치 (0) | 2022.08.18 |
| 백준 - 13549 숨바꼭질3 (0) | 2022.08.13 |
| 백준 - 12851 숨바꼭질2 (0) | 2022.08.13 |
| 백준 1679 - 숨바꼭질 BFS (0) | 2022.08.09 |
댓글