Algorithm/BOJ
-
[BOJ] 다리 만들기Algorithm/BOJ 2020. 9. 7. 18:33
[2146] 다리 만들기 https://www.acmicpc.net/problem/2146 Solution 먼저 각 섬을 구분하기 위한 Numbering 작업을 하고 map[][]의 모든 cell에 대해 바다가 아니면 BFS 탐색을 한다. BFS 탐색을 통해 섬의 끝부분에서 다른 섬까지의 최소값을 answer에 저장한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74..
-
[BOJ] 게리맨더링Algorithm/BOJ 2020. 9. 6. 19:48
[17471] 게리맨더링 https://www.acmicpc.net/problem/17471 Solution permutation 함수로 N개 구역을 두 선거구로 나눈다음 나뉘어진 선거구에 대해 인접한 선거구인지 체크하는 isConnected 함수를 호출한다. 각 선거구에 대해 dfs로 탐색했을 때 모든 지역을 방문했다면 인접한 선거구이다. answer에 인구 차이의 최솟값을 저장한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 6..
-
[BOJ] 파이프 옮기기 1Algorithm/BOJ 2020. 9. 6. 16:12
[17070] 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 Solution (0,1) 위치에서 부터 이동할 수 있는 모든 경우를 dfs로 탐색 대각선 파이프로 이동하는 경우에 빈칸이어야 하는 조건을 미리 고려해야한다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86..
-
[BOJ] 캐슬 디펜스Algorithm/BOJ 2020. 9. 6. 14:01
[17135] 캐슬 디펜스 https://www.acmicpc.net/problem/17135 Solution 문제에서 주어진 조건만 고려하면서 그대로 구현했다. 입력에서 주어진 격자판에서 마지막 행에 궁수를 배치할 수 있도록 map[N+1][M] 크기로 바꾸었다. permutation() 함수로 위치를 바꿔가며 세 명의 궁수를 배치 궁수의 위치가 정해지면 N번의 턴마다 shoot() 함수를 호출해 죽은 적의 수를 count 변수에 더해 가장 큰 값만 answer 변수에 가지고 있는다. shoot() 함수에서는 각 궁수의 위치로부터 d 거리 내의 가장 가까운 적을 죽인다. 유의해야할 부분은 가장 가까운 적을 동시에 죽이다 보니 표적이 되는 적이 중복되는 경우가 있으므로 세 명의 궁수에 대해 가까운 적을 ..
-
[BOJ] 동전 1, 동전 2Algorithm/BOJ 2020. 9. 3. 18:51
[2293] 동전 1 https://www.acmicpc.net/problem/2293 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(..
-
[BOJ] 영화감독 숌Algorithm/BOJ 2020. 8. 27. 01:11
[1436] 영화감독 숌 https://www.acmicpc.net/problem/1436 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { static int n; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int num = 0; ..
-
[BOJ] 괄호 추가하기Algorithm/BOJ 2020. 8. 26. 18:19
[16337] 괄호 추가하기 https://www.acmicpc.net/problem/16637 길이가 N인 수식이 주어진다. N은 1-9 숫자 혹은 {+, -, *} 연산자 연산자 우선순위는 모두 동일. 왼쪽부터 순서대로 계산 단 괄호를 추가했을 때는 괄호 안 수식 먼저 계산하여 중첩 괄호는 허용하지 않는다. 수식이 주어졌을 때, 괄호를 적절히 추가하여 식의 결과의 최댓값 구하는 문제 괄호의 수는 제한이 없으며 없어도 된다. 수식 길이 N(1 먼저 계산할 수식을 고르는 것 연산자는 최대 9개가 나올 수 있고, 9개를 모두 고르는 일 => 괄호가 하나도 없을 때 괄호는 중첩될 수 없으므로 ((3 ①+ 8) ②* 7) ③- 9 ④+ 2 의 ①, ② 연산자를 연속해서 뽑을 수 없다. 위 예에서는 1번 연산자..