데구리 블로그

문제 링크 www.acmicpc.net/problem/1376 1376번: 민식우선탐색 첫째 줄에는 정점의 개수 N(= '0' && c = k) return query(node * 2, s, m, k); else return query(node * 2 + 1, m + 1, e, k - leftCnt); } void removeEdge(int e) { int idx = lower_bound(ALL(edges), e) - edges.begin(); update(1, 0, treeSize - 1, idx, -1); numEdges--; } void update(int node, int s, int e, int idx, int diff) { if (s

문제 링크 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 다음과 같이 두 가지이다. 명령 1. Go k - k는 1, 2 또는 3일 수 있다. 현재 향하고 있는 방향으로 k칸 만큼 움직인다. 명령 2. Turn dir - dir은 left 또는 right 이며, 각각 왼쪽 또는 오른쪽으로 90° 회전한다. 공장 내 궤 www.acmicpc.net 풀이 로봇의 위치와 방향을 묶어 하나의 스테이트로 저장해서 BFS를 돌리면 됩니다. 한 스테이트에서 갈 수 있는 경우의 수는 앞으로 1,..

문제 링크 https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 문제 상근이와 선영이는 학교 숙제로 로봇을 만들고 있다. 로봇을 만들던 중에 구멍을 막을 두 레고 조각이 필요하다는 것을 깨달았다. 구멍의 너비는 x 센티미터이고, 구멍에 넣을 두 조각의 길이의 합은 구멍의 너비와 정확하게 일치해야 한다. 정확하게 일치하지 않으면, 프로젝트 시연을 할 때 로봇은 부수어질 것이고 상근이와 선영이는 F를 받게 된다. 구멍은 항상 두 조각으로 막아야 한다. 지난밤, 상근이와 선영이는 물리 실험실에 들어가서 레고 조각의 크기를 www.acmicpc.net 두 블록 길이의 합이 정확히 구멍의 길이와 같은 블록을 찾는 문제입니다. 풀이 1) 구멍의 너비 x의 단위는 센티미터이므로..

문제 링크 https://www.acmicpc.net/problem/15971 15971번: 두 로봇 2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사 www.acmicpc.net 두 로봇은 인접한 노드에 있으면 통신이 가능합니다. 풀이 1) 두 로봇 사이 최단 거리를 dfs로 구해줍니다. 2) 위에서..

문제 링크 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러스는 퍼지게 된다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 빈 칸은 바이러스를 놓을 수 있는 칸이다. 바이러스는 상하좌우로 www.acmicpc.net https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연..

문제 링크 https://www.acmicpc.net/problem/17392 17392번: 우울한 방학 1일, 5일, 8일에 약속을 순서대로 배치하면, 4일과 10일에 각각 1만큼의 우울함을 느끼게 되어, 총 2만큼의 우울함을 느끼게 된다. 이보다 덜 우울함을 느끼게 만드는 방법은 존재하지 않는다. www.acmicpc.net 모든 약속을 적절히 배치해서 우울함의 합을 최소로 만들면 됩니다. 어떤 약속의 기대행복값을 $H_i$라 하면, 그 약속이 있는 날을 포함해 $H_i+1$일 동안은 우울함을 느끼지 않습니다. 이를 수직선으로 생각해봅시다. 길이 $M$(방학의 일수)의 수직선 위에 길이가 서로 다른 수직선들(기대 행복값, 길이: $H_i+1$)을 적절히 배치하여 비어있는 구간의 길이에 따라 우울함의 ..

문제 링크 https://www.acmicpc.net/problem/17131 17131번: 여우가 정보섬에 올라온 이유 첫 줄에 별의 개수 N이 주어진다. 그 다음 줄부터 N개의 줄에 걸쳐 별의 좌표 x y가 주어진다. www.acmicpc.net 만들어질 수 있는 V형 별자리의 총개수를 구해야 하는 문제입니다. 우선 한 점을 기준으로, (왼쪽 위에 있는 모든 점의 개수)*(오른쪽 위에 있는 모든 점의 개수) 만큼의 V형 별자리를 만들 수 있습니다. 물론 $N \leq 200,000$이므로 한 점마다 매번 반복해서 점의 개수를 구하는 건 불가능합니다. 결론부터 말하면 구간 트리(세그먼트 트리, 펜윅 트리)를 이용해 풀 수 있습니다. 저는 펜윅 트리를 이용했습니다. 트리의 구간은 x축(수학에서의 x축)의..

문제 링크 https://www.acmicpc.net/problem/17127 17127번: 벚꽃이 정보섬에 피어난 이유 다음과 같이 나누는 것이 P의 합을 최대화 한다: [2] [5 3 1 4] [2] [3] www.acmicpc.net $N$개의 벚나무들을 네 개의 그룹으로 묶습니다. 이때 그룹에 포함되지 않은 벚나무가 없어야 하고, 같은 그룹의 벚나무들은 항상 연속하게 위치합니다. 예시로 다음처럼 그룹을 지을 수 있습니다. $N$이 작으니 그룹이 지어질 수 있는 모든 경우의 수를 하나하나 확인해보면 됩니다. 그걸 어떻게 구현하느냐, 모든 그룹은 연속적으로 놓여 있으므로 한 포인트를 지정해주면 그 포인트의 왼쪽 그룹이 끝나는 지점과 오른쪽 그룹이 시작하는 지점을 동시에 구할 수 있습니다. 첫 번째 그..

문제 링크 https://www.acmicpc.net/problem/1018 전체 보드를 8*8크기의 보드로 분할했을 때 분할된 보드가 체스판이 되기 위해 수정해야 하는 정사각형의 최솟값을 출력해야 합니다. 8*8 보드의 첫 칸의 좌표를 (0, 0)이라 했을 때, 좌표 (i, j)에서 i+j가 홀수인 칸들이 모두 같은 색이고, 짝수인 칸들이 모두 같은 색이어야 합니다. (0, 0) 정사각형이 흰색일 때와 검은색일 때를 모두 고려해서 수정해야 하는 정사각형의 수를 구하면 됩니다. 정답 코드 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 #include..

문제 링크 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 자리수가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 100 미만의 모든 수는 한수입니다. 1000은 한수가 아닙니다. 따라서 $n \geq 100$인 경우 1000을 제외한 100 ~ n까지만 확인해보면 됩니다. 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include #include using namespace std; int n..