BOBO's Note

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 풀이 방법 N개의 집 중 C개의 집에 공유기를 설치하는 모든 경우의 수는 이다. 각 경우의 수에 대하여 최소 인접 거리를 구하는 것은 O(C)의 시간이 걸리기 때문에 전체 시간복잡도는 이다. Brute force 방식으로 모든 경우의 수에 대하여 계산하면 시간 초과가 발생한다. 따라서 이진 탐색을 활용해 인접한 공유기 사이의 최소 거리를 찾아..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 풀이 방법 게임판을 저장하기 위해서 위와 같이 5개의 경로를 나누어 각 배열에 저장했다. 각 칸에 적혀진 값을 순서대로 저장한다. struct board { int route[21] = { -1, }; // on_route = 0 int route10[4] = { 10, 13, 16, 19 }; // on_route = 1 int route20[3] = { 20, 22, 24 }; // on_route = 2 int route30[4] = { 30, 28, 27, 26 }; // on_route = 3 int route25..

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 방법 A op B 구조(A, B: operand, op: operator)에서 해당 연산을 괄호로 묶는 경우, 안 묶는 경우를 DFS로 완전 탐색한다. new_expr에 표현식을 완성해나가는데, 괄호를 묶는 경우는 연산을 해준 값을 바로 저장해준다. 이때, 연산을 해준 값이 10 이상일 수 있기 때문에 new_expr을 char형 배열이 아닌 int형 배열로 선언했다. for..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 풀이 방법 물고기를 먹으려할 때마다 BFS를 이용해서 어떤 물고기를 먹을지 결정한다. 더 이상 먹을 수 있는 물고기가 없으면 종료한다. BFS를 사용하여 탐색할 때 큐에 행, 열, 아기 상어로부터의 거리를 추가한다. queue q; 아기 상어로부터 거리가 동일한 물고기가 여러 개 존재하면 더 작은 행에 위치하고, 동일한 행에 존재하면 더 작은 열에 존재하는 물고기를 선택..

https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크�� www.acmicpc.net 풀이 방법 1인 칸에 대해서 가능한 모든 색종이 종류를 덮어본다. DFS를 이용해서 1인 칸을 모두 덮은 경우, 사용한 최소 색종이 수를 업데이트해나간다. (i, j)를 왼쪽 꼭짓점으로 덮을 수 있는 모든 색종이 종류는 다음과 같이 구한다. 한 변의 길이가 n보다 큰 색종이는 0인 칸 또는 다른 색종이로 덮은 칸까지 덮는다. for(r=i; r 0){ if(!cover(i, j, k)..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 방법 모든 연산 순서 조합을 구해서 각 순서에 대해 연산을 차례대로 수행한 후, 그 중 최소 배열 값을 반환한다. 우선 연산 순서 조합을 구하는 함수는 min_val()이다. K개의 연산에 대해 순서 조합을 구하면 Arr 클래스의 apply_ops() 메소드를 호출해 배열 값을 계산한다. void min_val(int n, Arr& arr){ static boo..

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 풀이 방법 파이프의 양 끝의 위치와 놓여진 방향을 pipe라는 구조체에 저장한다. struct pos{ int r; int c; pos(int r_, int c_): r(r_), c(c_) {}; }; struct pipe{ pos start; pos end; int dir; pipe(pos start_, pos end_, int dir_): start(start_), e..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 풀이 방법 주어진 시간 내에 답을 찾기 위해서는 이진 탐색에 DP를 사용해 풀어야 한다. 그리고 std::cin/std::cout 보다는 scanf()/printf()를 사용해야 한다. 찾으려는 수를 key로, 존재 여부를 value로 갖는 unordered_map memo를 선언한다. 그 후, 탐색을 하기 전에 memo를 먼저 살펴봐 데이터가 없는 경..