728x90 그래프 이론18 [JAVA]백준 13549번: 숨바꼭질 3 www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 문제 설명 수빈이의 현재 위치를 N, 동생의 현재 위치를 K라고 할 때 수빈이가 이동하여 동생의 위치와 같아지는 가장 빠른 시간을 출력하는 문제이다. 수빈이의 현재 위치를 X라고 할 때 수빈이는 1초 후에 X-1, X+1 위치로 이동하고 0초 후에 X*2 위치로 이동할 수 있다. 2. 풀이 kwoncorin.tistory.com/70 [JAVA]백준 1697번: 숨바꼭질 .. 2021. 2. 19. [JAVA]백준 12851번: 숨바꼭질 2 www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 1. 문제 설명 수빈이의 현재 위치를 N, 동생의 현재 위치를 K라고 할 때 수빈이가 이동하여 동생의 위치와 같아지는 가장 빠른 시간과 가장 빠른 시간으로 찾는 방법의 가지 수를 출력하는 문제이다. 수빈이의 현재 위치를 X라고 할 때 수빈이는 1초 후에 X-1, X+1, 2*X 위치로 이동할 수 있다. 2. 풀이 kwoncorin.tistory.com/70?category=.. 2021. 2. 18. [JAVA]백준 1697번: 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 문제 설명 수빈이의 현재 위치를 N, 동생의 현재 위치를 K라고 할 때 수빈이가 이동하여 동생의 위치와 같아지는 가장 빠른 시간을 출력하는 문제이다. 수빈이의 현재 위치를 X라고 할 때 수빈이는 1초 후에 X-1, X+1, 2*X 위치로 이동할 수 있다. 2. 풀이 BFS로 풀 수 있는 문제이다. BFS로 위치들을 방문해가면서 현재 위치 X에서 다음 위치로 가능한 위치들(X+1,.. 2021. 2. 11. [JAVA]백준 12852번: 1로 만들기 2 www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. 문제 설명 정수 X에 사용할 수 있는 연산이 3가지가 있다. X/2, X/3, X-1 위의 세가지 연산을 사용하여 주어진 정수 N을 1로 만들려고 할 때 연산을 사용하는 횟수의 최솟값과 1로 만드는 방법을 출력하는 문제이다. 2. 풀이 DP를 이용해서 최솟값을 구하고 그 순간들의 선택을 배열로 저장하여 역추적할 수 있다. dp 배열에는 현재 정수 N을 1로 만들 수 있는 최솟값을 저장하고 trace 배열에는 연산을 사용하였을 때 N 전의 값이 무엇인지 저장한다. X/3 연산을 사용하여 연산 횟수의 최솟값을 구하.. 2021. 2. 5. 이전 1 2 3 4 5 다음 728x90
