티스토리 뷰
1. 문제
영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다.
영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다.
- 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다.
- 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.
- 화면에 있는 이모티콘 중 하나를 삭제한다.
모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 내용은 덮어쓰기가 된다. 클립보드가 비어있는 상태에는 붙여넣기를 할 수 없으며, 일부만 클립보드에 복사할 수는 없다. 또한, 클립보드에 있는 이모티콘 중 일부를 삭제할 수 없다. 화면에 이모티콘을 붙여넣기 하면, 클립보드에 있는 이모티콘의 개수가 화면에 추가된다.
영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.
입)
첫째 줄에 S (2 ≤ S ≤ 1000) 가 주어진다.
출)
첫째 줄에 이모티콘을 S개 만들기 위해 필요한 시간의 최솟값을 출력한다.
2. 풀이
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
class Pair {
// 화면에 출력된 문자 길이
int s;
// 클립보드에 복사되어 있는 문자 길이
int c;
public Pair(int s, int c) {
this.s = s;
this.c = c;
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
boolean[][] check = new boolean[n+1][n+1];
int[][] dist = new int[n+1][n+1];
Queue<Pair> queue = new LinkedList<>();
// 시작점
queue.add(new Pair(1, 0));
check[1][0] = true;
dist[1][0] = 0;
while (!queue.isEmpty()) {
Pair p = queue.poll();
// 1. 클립보드에 복사
if (!check[p.s][p.s]) {
queue.add(new Pair(p.s, p.s));
check[p.s][p.s] = true;
dist[p.s][p.s] = dist[p.s][p.c] + 1;
}
// 2. 붙여넣기
if (p.s + p.c <= n && !check[p.s+p.c][p.c]) {
queue.add(new Pair(p.s+p.c, p.c));
check[p.s+p.c][p.c] = true;
dist[p.s+p.c][p.c] = dist[p.s][p.c] + 1;
}
// 3. 하나 삭제
if (p.s - 1 >= 0 && !check[p.s-1][p.c]) {
queue.add(new Pair(p.s-1, p.c));
check[p.s-1][p.c] = true;
dist[p.s-1][p.c] = dist[p.s][p.c] + 1;
}
}
int answer = Integer.MAX_VALUE;
// 클립보드에 몇 개가 있을 때 최소인지 알 수 없으므로
for (int i = 0; i <= n; i++) {
if (check[n][i] && answer > dist[n][i]) {
answer = dist[n][i];
}
}
System.out.println(answer);
}
}
BFS를 사용해서 해결.
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 비동기
- a
- 논블로킹
- http://www.nextree.co.kr/p6960/
- blocking
- 프로그래머스 Level 3
- 프로그래머스 Level 1
- 인터셉터
- non-blocking
- 핸들러 인터셉터
- 프로그래머스 Level 2
- Filter
- 스택/큐
- 필터
- Asynchronous
- 해시
- 프로그래머스
- 동기
- 코딩테스트 고득점 Kit
- Handler Interceptor
- Synchronous
- 블로킹
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
글 보관함