전체 글(724)
-
[백준/BOJ] 백준 2472번 : 체인점
https://www.acmicpc.net/problem/2472 2472번: 체인점 첫째 줄에는 매장 후보지의 개수를 나타내는 정수 N이 입력된다(1 ≤ N ≤ 100,000). 매장 후보지들은 1부터 N까지의 번호로 구분된다. 둘째 줄에는 아파트 단지의 위치를 나타내는 세 개의 정수 A, B, www.acmicpc.net 각 아파트로부터 각 매장 후보지까지 최단 거리를 구하고, 후보지 번호를 A 아파트로부터 거리 순으로 정렬한 뒤 A 아파트로부터 거리가 짧은 후보지부터 매장을 설치할 수 있는지 확인했다. 후보지가 매장을 설치할 수 있는지 확인하기 위해서 해당 후보지가 다른 후보지보다 A, B, C 아파트와의 거리가 모두 긴 경우가 있지 않은지 확인해야 했는데, 우선 A 아파트와의 거리 비교는 A 아파..
2023.03.31 -
[백준/BOJ] 백준 17306번 : 전쟁 중의 삶
https://www.acmicpc.net/problem/17306 17306번: 전쟁 중의 삶 석환나라에 전쟁이 일어났다! 석환나라는 엄청나게 큰 이진 트리 모양의 국가로, 1,2, ... ,10100 까지 번호가 붙여진 총 10100 개의 도시로 이루어져 있다. 석환나라에는 10100-1개의 도로가 있는데, www.acmicpc.net 군부대가 있는 도시의 숫자를 2진수 비트로 표현한 뒤, 해당 2진수 비트를 트라이로 표현해서 만들어지는 트라이의 노드의 개수를 구하고 트라이에서 군부대 도시 노드들의 최소 공통 조상(LCA) 노드 위에 있는 노드들(위험하지 않은 도시)의 개수를 빼서 위험한 도시의 개수를 구하는 방법으로 문제를 해결했다. 다음 이미지는 군부대가 있는 도시의 번호가 8,9 일 때 예시이다..
2023.03.30 -
[백준/BOJ] 백준 10218번 : Maze
https://www.acmicpc.net/problem/10218 10218번: Maze 각 테스트 케이스마다 한 줄을 출력한다. 빈 칸 어디에 공이 있든, 10회 이내에 항상 공을 빼낼 수 있는 방법이 존재한다면, 'L','R','U','D'로 이뤄진 문자열을 하나 출력한다. 각각 왼쪽으로 기울이 www.acmicpc.net 빈칸인 경우 공이 있을 수 있는 위치이므로, 공이 있을 수 있는 빈칸의 위치들을 저장해 놓고 각 위치에서 왼쪽으로 기울기, 위쪽으로 기울기, 오른쪽으로 기울기, 아래쪽으로 기울기를 했을 때 경우를 확인해 가는 방식을 통해 문제를 해결했다. 기울이는 방향을 정할 때 이전에 움직였던 방향과 같은 방향으로 움직이는 것은 의미가 없으므로, 이전에 움직였던 방향으로는 또 다시 움직이지 않..
2023.03.30 -
[백준/BOJ] 백준 17522번 : Canal
https://www.acmicpc.net/problem/17522 17522번: Canal It is quite recent that more people started to settle in Aissippissi, a small town located in a flat and dry desert. Aissippissi is still under development, and the government planned to construct a canal across the town. The canal will consist of two long www.acmicpc.net 이분 탐색을 통해 모든 좌표끼리 거리가 x좌표 또는 y좌표를 기준으로 특점 범위 이내로 만들 수 있는지 확인하는 방법을 통해 좌표끼..
2023.03.23 -
[백준/BOJ] 백준 20933번 : 마스크펑크 2077
https://www.acmicpc.net/problem/20933 20933번: 마스크펑크 2077 때는 2077년, 끝나지 않는 전염병의 확산으로 모든 가정에서 가내수공업으로 마스크를 만들 수 있게 된다. 하지만 개개인의 기술력에 차이가 있어서, 마스크의 생산 비용이 집마다 달랐다. $N$개 www.acmicpc.net 구간의 범위에 대해 마스크 생산 비용의 최솟값 세그먼트 트리와, 이동시간의 합 세그먼트 트리를 만들었다. 그리고 난 뒤, 주어진 시간 내에 이동할 수 있는 범위를 이분 탐색을 통해 구하고 구한 범위의 최소 마스크 가격을 세그먼트 트리의 쿼리를 통해 찾아서 문제를 해결했다. 코드 #include #include #include #include #include using namespace..
2023.03.23 -
[백준/BOJ] 백준 3114번 : 사과와 바나나
https://www.acmicpc.net/problem/3114 3114번: 사과와 바나나 첫 번째 예제의 경우 불도저가 오른쪽-아래, 오른쪽-아래, 아래로 이동하면 된다. 경로의 아래에 있는 사과 나무의 개수는 3+2+4=9개이고, 위에 있는 바나나 나무의 개수는 3+5=8개이다. www.acmicpc.net 사과의 개수와 바나나의 개수를 각각 2차원 배열에 표시해 놓고 사과의 경우 열마다 누적합을 저장하고, 바나나의 경우 행마다 누적합을 저장해 놓은 뒤, 불도저의 출발 지점인 왼쪽 위부터 도착 지점인 오른쪽 아래까지 이동하며 아래쪽의 사과와 위쪽의 바나나 개수의 최대 합을 다이나믹 프로그래밍(DP)을 통해 계산했다. 이때 불도저가 움직이면서 추가되는 범위의 사과의 개수와 바나나의 개수는 이전에 저장..
2023.03.21