문제 설명도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/2110 제한 사항 풀이문제를 요약하면, N개의 집이 주어지고 C개의 공유기를 설치해야 한다.C개를 최대한 넓은 간격으로 설..
문제 설명도시에서 태양이 질 때에 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다.정확히 건물이 몇 개 있는지 알아내는 것은 대부분의 경우에 불가능하고, 건물이 최소한 몇 채 인지 알아내는 것은 가능해 보인다. 이를 알아내는 프로그램을 작성해 보자.https://www.acmicpc.net/problem/1863 제한 사항 풀이문제를 요약하면, 빌딩의 높이가 변경될 때 x, y좌표가 x의 오름차순으로 주어질때, 최소한의 빌딩의 개수를 구하는 것이다.문제를 글로만 읽으면 이해하기 어려울 수 있다.예시를 봐보자.101 12 25 16 38 111 015 217 ..
문제 설명1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.https://www.acmicpc.net/problem/7490 제한 사항 풀이문제를 요약하면, 1부터 N까지 연속한 수열의 사이에 연산자를 추가하여 0을 만들 수 있는 경우를 출력하는 것이다.이때, 연산자는 총 3개이다.+: 더하기-: 빼기' ': 이어 붙이기 해당 문제는 dfs(재귀)를 통해 해결할 수 있다.+와..
문제 설명세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바..
문제 설명2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? 제한 사항 풀이문제를 요약하면, 2차원의 블록의 높이에 대한 입력이 주어지면 그 블록들 사이에 고이는 물의 양을 구하는 것이다.예를 들어,검은색은 블록을 나타내며 하늘색은 물을 나타낸다.위의 경우 고이는 물의 양은 5이다. 해당 문제를 해결하는 방법은 간단하다.물은 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록 중 낮은 높이에 맞춰 고이게 된다.1번 기둥(높이:1)의 경우, 왼쪽은 0번 기둥(높이:3)이 가장 높고 오른쪽은 4번 기둥(높이:4)이 가장 높은기둥이다.이 중, 낮은 기둥인 0번 기둥의 높이에서 자신의 높이의 차이로 물이 고이게 된다...
문제 설명작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.알파벳 소문자로 이루어진 문자열 W가 주어진다.양의 정수 K가 주어진다.어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다.어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다.위와 같은 방식으로 게임을 T회 진행한다.https://www.acmicpc.net/problem/20437 제한 사항 풀이문제를 요약하면, 문자열 w가 주어졌을 때, K개의 문자를 포함하는 가장 짧은 연속 부분 문자열의 길이와 K개의 문자를 포함하며 양끝으로 하는 가장 긴 문자열의 길이를 구하는 것이다. 처음에는 투포인터 혹은 DP로 ..
문제 설명빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다.이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.문자열의 뒤에 A를 추가한다.문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오. https://www.acmicpc.net/problem/12919 제한 사항 풀이문제를 요약하면, S와 T 두 문자열이 주어지면 S를 T..
문제 설명빨간색 볼과 파란색 볼이 에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.예를 들어, 처음에 볼이 에서 보인 것처럼 있을 때, 빨간 볼을 에서 보인 것처럼 옮긴 후, 에서 ..
문제 설명a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.예를 들어, aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.https://www.acmicpc.net/problem/1522 제한 사항 풀이문제를 요약하면, a와 b로만 이루어진 문자열이 주어지면 적절히 문자를 바꿔 a가 연속하도록 바꿔야 한다.a가 연속하도록 변경하려면 최소 몇 번 바꿔야 하는지 계산해야 한다. 해당 문제는 접근법만 정립하면 간단하게 풀리는 문제이다.a가 연속하다는 얘기는 b도 연속하다는 얘기가 된다.b사이에 a가 존..
문제 설명홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. $100,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다. 이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자. 제한 사항 풀이문제를 요약하면, N개의 수가 주어질 때, K개 이하로 중복을 허용하는 가장 긴 부분 수열의 길이를 구하는 것이다. 해당 문제의 부분 수열은 연속적이어야 하기 때문에 deque를 사용하여 앞, 뒤를 붙이거나 제거하며 풀어나가면 된다.예를 들면, $K = 2$인 상..
