문제#
- 링크로 대체
풀이 및 주저리..
오프라인 수업때 풀지 못했던 이모티콘 문제를 드디어 풀었다.. 근래에 바빠서 일주일에 한두개 정도밖에 알고리즘 문제를 못풀고 있는데 이번에 오는 면접이후에 다시금 열심히 할 수 있도록 해야할것 같다. 최근에 문제는 가능하면 DFS 와 BFS 관련 문제를 집중적으로 풀고있는데 이 문제는 BFS 문제이다. 단순하게 BFS에서 좀 더 생각을 해야 풀 수 있는 문제였는데, 지금 그린 이모티콘을 저장하는 것을 따로 배열로 만들고 이차원배열로 상황을 하나하나 비교하며 풀어나갔다.
코드
package baekjoon.algorithm.day02;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
public class Emoticon {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] list = new int[N + 1][N +1];
for (int i = 0; i < N + 1; i++) {
Arrays.fill(list[i], -1);
}
Queue<Integer> que = new LinkedList<>();
list[1][0] = 0;
que.add(1);
que.add(0);
while (!que.isEmpty()) {
int now = que.poll();
int copy = que.poll();
if (now + copy < N + 1 && list[now + copy][copy] == -1) {
list[now + copy][copy] = list[now][copy] + 1;
que.add(now + copy);
que.add(copy);
}
if (list[now][now] == -1) {
list[now][now] = list[now][copy] + 1;
que.add(now);
que.add(now);
}
if (now -1 >= 0 && list[now - 1][copy] == -1) {
list[now - 1][copy] = list[now][copy] + 1;
que.add(now - 1);
que.add(copy);
}
}
int answer = -1;
for (int i = 0; i < N + 1; i++) {
if(answer == -1 || answer > list[N][i])
answer = list[N][i];
}
System.out.println(answer);
}
}기억에 남길 것!
- 무