본문 바로가기

알고리즘/BAEKJOON34

[백준] 11660 구간 합 구하기 5 (Java) [11660 구간 합 구하기 5] 난이도: 실버1 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 입력 출력 [아이디어] DP를 사용하여 구하면 된다. D[x1][y1] = (1, 1)부터 (x1, y1)까지의 누적 합을 나타낸다. 보라색 부분을 구하기 위해서는 D[3][4] - D[2][4] - D[3][1] + D[2][1] 을 구하면 되다. D[2][1]을 다시 더해주는 이유는 그 부분이 두번 빠지기 때문이다. [JAVA 코드] import java.io.*.. 2022. 6. 23.
[백준] 14503 로봇 청소기 (Java) [14503 로봇 청소기] 난이도: 골드5 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 문제 입력 출력 [아이디어] 문제에 써있는 설명대로 코드를 작성해주면 되는 시뮬레이션 문제이다. 조심해야되는 부분은 후진할 때는 청소를 한 장소여도 후진할 수 있다. 그리고 후진한 후 청소를 다시 해주면 안된다는 것이다. 청소하지 않은 장소인 경우에만 청소해주자. [JAVA 코드] package bj.g5; import java.io.*; import java.util.*; public class BJ_G5_14503_.. 2022. 6. 6.
[백준] 17779 게리맨더링2 (Java) [17779 게리맨더링2] 난이도: 골드4 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 문제 입력 출력 [아이디어] 가능한 모든 경우들을 완탐으로 풀었다. 1, 2, 3, 4번 선거구역을 나눠주고 해당되지 않는 구역을 5번 구역으로 판단해서 값을 구해줬다. 여기서 선거구역을 나눌 때 경계선의 꼭지점들을 기준으로 판단해주었다. 예를 들면, x = 4, y = 3, d1 = 1, d2 = 1 의 경우 1번 선거구역을 찾기 위해 (x, y) => (4, 3) 을 기준으로 위에 있는 칸들을 먼저 찾아주고 r이 3이하인 .. 2022. 6. 3.
[백준] 2141 우체국 (Java) [2141 우체국] 난이도: 골드4 2141번: 우체국 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다. www.acmicpc.net 문제 입력 출력 [아이디어] 입력할 때 우체국 위치 순서대로 입력한다는 말은 없기 때문에 중간에 정렬을 해줘야한다. 전체 인구 수의 절반 이상이 넘어가면 그 위치가 정답이 된다. 하지만 전체 인구 수가 홀수일 수 있어서 1을 더한 값으로 계산해줘야한다. [JAVA 코드] import java.io.*; import java.util.*; publ.. 2022. 6. 3.
[백준] 13265 색칠하기 (Java) [13265 색칠하기] 난이도: 골드5 13265번: 색칠하기 각 테스트 케이스에 대해서 possible 이나 impossible 을 출력한다. 2 가지 색상으로 색칠이 가능하면 possible. 불가능하면 impossible 이다. www.acmicpc.net 문제 입력 출력 [아이디어] 먼저 동그라미들을 노드로 갖고 연결된 직선을 엣지로 생각해주었다. 그 후 노드에 대해 DFS를 사용하여 연결된 노드 두개가 같은 색이라면 impossible, 아니라면 possible을 출력하도록 하였다. [JAVA 코드] import java.io.*; import java.util.*; public class BJ_G5_13265_색칠하기 { static BufferedReader br = new BufferedR.. 2022. 5. 29.
[백준] 11653 소인수분해 (Java) [11653 소인수분해] 난이도: 실버5 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 나누는 수가 소수인지 판단해주는 방식을 사용하였다. 그런데 계속 시간 초과가 떴다. 왜 그럴까 생각해보니 이미 소수이면 해당 수로 다 나누기 때문에 그의 배수로는 나눌 수 없다. 예를 들면 12 = 2 x 2 x 3 이다. 이 때, 12 % 2 == 0 이므로 12 / 2 = 6 / 2 = 3 을 만들어버린다. 따라서 이후에 4, 6, 8 등으로는 나눌 수 없게 된다. 물론 그 전에 수가 1이 된다면 반복문을 빠져나온다. [JAVA 코드] import java.io.*; public class Main {.. 2022. 5. 26.
[백준] 2580 스도쿠 (Java) [2580 스도쿠] 난이도: 골드4 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 문제 입력 출력 [아이디어] 스도쿠에 빈칸들을 따로 저장해주었고, 행, 열, 사각형에 같은 숫자가 있는지 빠르게 체크해주기 위해서 배열을 따로 생성해주었다. static boolean [][] row = new boolean [9][10]; static boolean [][] col = new boolean [9][10]; static boolean [][] square = new boolean [9][10]; row[i][j.. 2022. 5. 21.
[백준] 11509 풍선 맞추기 (Java) [11509 풍선 맞추기] 난이도: 골드5 11509번: 풍선 맞추기 첫 번째 예제 에서 [5,4,3] 을 터트리고 [2,1]을 터트리면 모든 풍선을 터트릴 수 있으므로 최소한 2개의 화살을 필요로 한다. www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 남아있는 풍선 중 가장 높이 있는 풍선의 높이를 찾아주기 위해 풍선들을 모두 탐색하려고 하였다. 하지만 풍선의 개수가 100만개이므로 모든 풍선이 다 터질 때까지 계속 반복하면 시간초과가 난다. 따라서 풍선 중 가장 높이 있는 높이를 구해주기 위해 우선순위 큐를 사용하였다. [JAVA 코드] import java.io.*; import java.util.*; public class Main { static BufferedReader br.. 2022. 5. 20.
[백준] 15681 트리와 쿼리 (Java) [15681 트리와 쿼리] 난이도: 골드5 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 입력 출력 [아이디어] 처음에는 트리를 생성해준 뒤 쿼리 개수만큼 정점의 수를 구했는데, 시간 초과가 났다. 그래서 문제 아래 있는 힌트대로 정점의 개수를 구하는 함수를 구현해주었다. [JAVA 코드] import java.io.*; import java.util.*; public class Main { static BufferedReader br = n.. 2022. 5. 20.
[백준] 17141 연구소2 (Java) [17141 연구소2] 난이도: 골드4 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 문제 입력 출력 [아이디어] 바이러스가 들어갈 자리에서 M개를 조합으로 선택하여 완전 탐색하는 방법이다. 사방면으로 바이러스가 퍼져나갈 수 있고, 최소 시간을 구하는 문제이기 때문에 BFS를 사용하였다. 그 외는 단순한데, Queue에 처음 바이러스 자리 M개를 초기화 시켜줄 때 전체 맵을 탐색할지 M개를 바로 넣을지를 고민하였다. 직접 해본 시간이 별로 차이나지 않으므로 아무거나 써도 될 것 같다! [JAVA 코드] 1. M개를 바.. 2022. 5. 20.
[백준] 21924 도시건설 (Java) [21924 도시건설] 난이도: 골드4 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 문제 입력 출력 [아이디어] 모든 노드를 이었을 때 가중치가 최소가 되어야 하므로 MST를 사용하였다. 기본적인 MST를 활용하였는데 모든 건물이 연결되지 않은 경우도 있기 때문에 방문한 노드의 수를 체크해주었다. 모든 가중치를 계산한 후 방문한 노드의 수가 전체 노드의 수 보다 적다면 연결되지 않은 경.. 2022. 5. 14.
[백준] 3584 가장 가까운 공통 조상 (Java) [3584 가장 가까운 공통 조상] 난이도: 골드4 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 입력 출력 [아이디어] 노드마다 부모는 단 하나만 존재한다. 그래서 노드의 부모를 저장해주는 배열을 따로 만들어주었다. parent[i] = j => i 의 부모가 j 이다. 그 다음 두 노드 중 하나의 노드부터 시작하여 루트까지 방문을 체크해준다. 그 후 나머지 노드에 대해 루트까지 올라가면서 방문한 노드를 만나면 그게 가장 가까운 공통 노드가 된다! .. 2022. 5. 12.

티스토리툴바