Algorithm/BOJ
-
[BOJ] 배열 돌리기 1Algorithm/BOJ 2020. 2. 10. 22:39
[16926] 배열 돌리기 1 https://www.acmicpc.net/problem/16926 배열의 크기(N,M), 회전의 수(R), 배열 정보가 주어졌을 때 배열을 반시계 방형으로 R번 회전시킨 결과를 구하는 문제 Solution 코테에서 자주 나오는 유형이니 외워두자. 시간 안습 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859import java.util.Scanner; public class Main { static int n, m, r; static int[] dx = { 0, 1, 0, -1 }; static int[] dy = { 1..
-
[BOJ] 게리멘더링Algorithm/BOJ 2020. 2. 10. 00:53
[17471] 게리멘더링 https://www.acmicpc.net/problem/17471 백준시는 N개의 구로 나누어져 있고, 1번부터 N번까지 번호가 매겨져 있다. 문제 조건 1. 구역을 두 개의 선거구로 나워야 하고, 선거구는 구역을 적어도 하나 포함해야 한다. 2. 한 선거구에 포함되어 있는 구역은 모두 연결되어야 한다. 공평하게 선거구를 나누기 위해 선거구에 포함된 인구의 차이를 최소로 하려고 한다. 위 조건을 만족하는 인구 차이의 최솟값을 구하는 문제 Solution permutation()을 사용한 DFS 풀이 방법 permutation()으로 두 개의 선거구를 나누었고, DFS를 사용해 선거구역의 연결 여부를 확인하였다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14..
-
[BOJ] 캠프 준비Algorithm/BOJ 2020. 2. 8. 23:15
[16938] 캠프 준비 https://www.acmicpc.net/problem/16938 캠프에 사용할 문제를 고르는 방법의 수를 구하는 문제 N : 가지고 있는 문제 수 L : 문제 난이도 하한 R : 문제 난이도 상한 X : 가장 쉬운 문제와 가장 어려운 문제 난이도 차이 1. 문제는 두 문제 이상 2. 뽑은 문제의 난이도는 L 이상 R 이하 3. 가장 쉬운 문제와 가장 어려운 문제의 난이도 차이는 X와 같거나 커야한다. Solution permutation 활용 문제 문제는 두 문제 이상이어야 하기 때문에 2 ~ N까지 size를 바꿔가면서 permutation() 함수를 돌렸다. 뽑은 문제를 temp 리스트에 담아 문제의 조건에 부합하면 count++를 해주었다. 소스코드 import java..
-
[BOJ] 연구소 2Algorithm/BOJ 2020. 2. 8. 21:51
[17141] 연구소2 https://www.acmicpc.net/problem/17141 바이러스를 놓을 수 있는 칸(arr[i][j] = 2)에 주어진 M개의 바이러를 놓았을 때 모든 빈 칸(arr[i][j] = 0)에 바이러스를 퍼뜨리는 최소 시간을 구하는 문제 0은 빈 칸, 1은 벽, 2는 바이러스를 놓을 수 있는 칸이다. 바이러스를 어떻게 놓아도 모든 빈 칸에 바이러스를 퍼뜨릴 수 없는 경우에는 -1을 출력한다. Solution permutation()을 사용한 BFS 문제 바이러스를 놓을 수 있는 칸의 좌표를 리스트에 모두 담고, permutation() 함수를 돌려 M개의 좌표를 뽑은 후에 BFS로 바이러스를 퍼뜨린다. 소스코드 import java.util.ArrayList; import ..
-
[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..