Algorithm
-
[BOJ] 치킨 배달Algorithm/BOJ 2020. 2. 8. 18:04
[15686] 치킨 배달 https://www.acmicpc.net/problem/15686 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다. 도시의 치킨집 중 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시키려 한다. 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오 Solution permutation()으로 치킨집 중 M개만 골라 치킨거리를 계산한다. 소스코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int n, m, min..
-
[BOJ] 배열 돌리기 4Algorithm/BOJ 2020. 2. 8. 15:24
[17405] 배열 돌리기 4 https://www.acmicpc.net/problem/17406 배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구하는 문제 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다. Solution permuation() 함수를 돌려 회전 순서를 바꿔가면서 simulation한다. 어렵다 T.T 소스코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int n, m, k, min = Integer.MAX_VALUE; static in..
-
[BOJ] DSLRAlgorithm/BOJ 2020. 2. 7. 17:41
[9019] DSLR https://www.acmicpc.net/problem/9019 네 자리 숫자 A와 B가 주어졌을 때 A -> B로 바꾸는 최소 연산 횟수 D : N -> 2*N S : N -> N-1 L : 한 자리씩 왼쪽으로 R : 한 자리씩 오른쪽으로 Solution BFS 풀이방법 이 문제는 어떠한 과정을 거쳐야 하는지를 구해야 한다. Register 객체를 만들어 연산을 했을 때 어떤 과정을 거쳤는지 저장한다. 123에 L 연산을 수행했을 때는 231이 아닌 1230이 계산 결과가 된다. 소스코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public st..
-
[BOJ] 숨바꼭질 2Algorithm/BOJ 2020. 2. 7. 14:35
[12851] 숨바꼭질 2 https://www.acmicpc.net/problem/12851 수빈이의 위치 : N 동생의 위치 : K 동생을 찾는 가장 빠른 시간을 구하는 문제, 그리고 그러한 방법의 개수도 구해야 한다. 수빈이가 할 수 있는 행동 (위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동(1초) 2. 순간이동 : 2 * X로 이동 (1초) Solution BFS 풀이 방법 경우의 수는 다이나믹 프로그래밍으로 구할 수 있다. cnt[i] = i 까지 가는 방법의 개수 이미 방문을해서 방문을 할 수 없는 경우에 거리가 같으면 방법의 수만 증가해준다. cnt[next] += cnt[cur]; 소스코드 import java.util.LinkedList; import java.util.Q..
-
[BOJ] 숨바꼭질 4Algorithm/BOJ 2020. 2. 6. 21:49
[13913] 숨바꼭질 4 https://www.acmicpc.net/problem/13913 수빈이의 위치 : N 동생의 위치 : K 동생을 찾는 가장 빠른 시간과 이동하는 방법을 구하는 문제 수빈이가 할 수 있는 행동 (위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동 (1초) 2. 순간이동 : 2 * X로 이동 (1초) Solution BFS 풀이 방법 d[] 배열에 이전 위치를 기억 하면서 걷기, 순간 이동을 한다. 동생을 찾으면 K 위치에서 N 위치까지 역학적으로 경로를 path 리스트에 추가한다. 소스코드 import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanne..
-
[BOJ] 숨바꼭질 3Algorithm/BOJ 2020. 2. 5. 17:36
[13549] 숨바꼭질 3 https://www.acmicpc.net/problem/13549 수빈이의 위치 N 동생의 위치 K 동생을 찾는 가장 빠른 시간을 구하는 문제 수빈이가 할 수 있는 행동(위치 : X) 1. 걷기 : X + 1 또는 X - 1로 이동 (1초) 2. 순간이동 : 2 * X로 이동(0초) Solution 덱을 사용한 BFS 풀이 방법 걷기와 순간이동의 가중치(시간)가 다르기 때문에 덱을 사용해 순간 이동은 덱의 앞에, 걷기는 덱의 뒤에 넣는 방법도 생각해 볼 수 있다. 소스코드 import java.util.Arrays; import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public clas..
-
[BOJ] 스타트와 링크Algorithm/BOJ 2020. 2. 5. 14:14
[14889] 스타트와 링크 https://www.acmicpc.net/problem/14889 N명을 N/2명씩 두 팀으로 나누려고 한다. (4 = a[i]) i -= 1; if (i = a[j]) j -= 1; swap(a, i - 1, j); j = n - 1; while (i < j) { swap(a, i, j); i += 1; j -= 1; } return true; } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public void print(int[] arr) { for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + "..
-
[BOJ] 단어 수학Algorithm/BOJ 2020. 2. 4. 19:11
[1339] 단어 수학 https://www.acmicpc.net/problem/1339 단어 수학은 0부터 9까지의 수를 알파벳 하나로 나타낸 것이다. N개의 간어를 수로 바꾼 다음에, 합의 최대값을 구하는 문제이다. (1 0 && a[i - 1] >= a[i]) i -= 1; if (i = a[j]) j -= 1; swap(a, i - 1, j); j = n - 1; while (i < j) { swap(a, i, j); i += 1; j -= 1; } return true; } public void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args)..