본문 바로가기

HWK블로그132

13913번 - 숨바꼭질4(bfs) 드디어 마지막 숨바꼭질 문제다.문제:수빈이는 N, 동생은 K 번째 점에 있다. 수빈이는 위치가 X일 때 1초 후에 X-1 또는 X+1 또는 2*X의 위치로 이동할 수 있다.수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법을 구하시오.첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.풀이:이전 숨바꼭질 문제들과 같이 bfs를 활용하여 푸는 문제이다.수빈이가 현 위치에서 다음 위치로 갈때, 다음 위치에 현 위치에서 출발했다는 흔적을 남기고,역순으로 출력해주면 문제가 풀릴 것이다.이를 위한 코드는 아래와 같다.static void bfs() { Queue queue = new LinkedList(); qu.. 2024. 7. 30.
13549번 - 숨바꼭질3(bfs) 문제:수빈이는 N, 동생은 K 번째 점에 있다. 수빈이는 위치가 X일 때 1초 후에 X-1 또는 X+1으로 이동할 수 있고,0초 후에 2*X의 위치로 순간이동할 수 있다.수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 풀이:수빈이와 동생은 모두 0 ~ 100,000 사이 점에 위치한다. x는 0과 100,000을 넘어갈 수 없다.그렇다면 BFS와 우선순위 큐를 사용해 수빈이가 가장 먼저 K에 도착하는 순간 그 시간을 반환해주면 될 것이다.우선순위 큐를 이용하기 위해 아래 클래스를 작성한다.class Node imp.. 2024. 7. 29.
12851번 - 숨바꼭질2(bfs) 문제:수빈이는 N, 동생은 K 번째 점에 있다. 수빈이는 위치가 X일 때 1초 후에 X-1 또는 X+1 또는 2*X의 위치로 이동할 수 있다.수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오.첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 풀이:수빈이가 어떤 위치로 이동하기 위해서는 X-1 또는 X+1 또는 2*X 로 이동 할 수 있다.가장 빠른 시간 안에 찾는 경우의 수를 구해야 하므로 BFS를 사용하면 될 것이다.일일히 진행하며 모든 수를 저장하고, 일일히 꺼내 쓰는 방법은, 너무 많은 저장공간을 요구한다.그래서 아래와 같이 생각을 해보았다. 두개의 스택 st.. 2024. 7. 28.
16953번 - A->B 문제: 정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최 솟값에 1을 더한 값을 출력하라. 풀이:비록 dfs, bfs 과정에 나와있으나, 전혀 쓰지 않는것이 더 좋은 방법이다.최솟값이라는 말이 잘못된 것이, 하나의 경우밖에 나오지 않는다. 이유는 예제 3을 보면 알 것이다.예제 3의 예시에는 100 → 200 → 2001 → 4002 → 40021 이 나와있다.100부터 시작하지말고 40021부터 시작해보자.40021 → 4002 →  2001 →  200 →  100그렇다면 이때 경우는 2로 나눈다.가장 오른쪽에서 1을 뺀다.이 두가지이다. 2로 나누려면 짝수여야 하며, 1을 오른쪽에서 빼려면 한.. 2024. 7. 25.

티스토리툴바