데구리 블로그

문제 링크 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$)을 적절히 배치하여 비어있는 구간의 길이에 따라 우울함의 ..

최대 연속 부분합 최대 연속 부분합이란 어떤 수열 $a_1, a_2, ..., a_{N}$이 주어졌을 때 $1 \leq i \leq j \leq N$ 를 만족하는 $sum(a_i, a_{i+1}, ..., a_j)$ 중 최댓값을 뜻합니다. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이 문제를 예로 들어봅시다. 쉽게 떠올릴 수 있는 풀이는 어떤 $(i, j)$에 대해 $sum(a_i, a_{i+1}, ..., a_j),(1 \leq i \leq j \..

혼자 그림 그려보면서 끙끙대다가 질문을 올렸는데 친절하신 분이 답변해주셨다. 앞쪽 부분의 개수를 정확히 구했으면 아래 싸이트에 수열을 넣고 검색해보라 하셨음. https://oeis.org/ The On-Line Encyclopedia of Integer Sequences® (OEIS®) oeis.org N = 2 $\longrightarrow$ 답 = 1 N = 4 $\longrightarrow$ 답 = 2 N = 6 $\longrightarrow$ 답 = 5 N = 8 $\longrightarrow$ 답 = 14 1, 2, 5, 14를 넣어보니 카탈란 수 라고 한다. $i$번째 카탈란수 $C_i = {2i\choose i} - {2i\choose i+1}$ 이다. 문제의 제한에서 N은 짝수이므로 $C..

문제 링크 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..