분류 전체보기

문제 설명a와 b로만 이루어진 문자열이 주어질 때,  a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오.이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 있는 것이다.예를 들어,  aabbaaabaaba이 주어졌을 때, 2번의 교환이면 a를 모두 연속으로 만들 수 있다.https://www.acmicpc.net/problem/1522      제한 사항      풀이문제를 요약하면, a와 b로만 이루어진 문자열이 주어지면 적절히 문자를 바꿔 a가 연속하도록 바꿔야 한다.a가 연속하도록 변경하려면 최소 몇 번 바꿔야 하는지 계산해야 한다. 해당 문제는 접근법만 정립하면 간단하게 풀리는 문제이다.a가 연속하다는 얘기는 b도 연속하다는 얘기가 된다.b사이에 a가 존..

문제 설명매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다.세준이가 운전해야 하는 거리의 최솟값을 출력하시오.      제한 사항      풀이문제를 요약하면, 0부터 D까지 이동하는데 지름길이 존재한다.지름길은 시작점, 도착점, 지름길의 거리 순으로 정보가 주어진다.지름길을 이용하여 D에 최소한의 거리를 이동하여 도착하면 된다. 처음 문제를 풀었을 때는 우선순위 큐를 이용하여 0에서 D까지 이동하며 거리를 갱신했다.지름길이 없는 경우도 있으니 현재 지점에서 1씩 더해 다음..

문제 설명홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. $100,000$ 이하의 양의 정수로 이루어진 길이가 $N$인 수열이 주어진다.  이 수열에서 같은 정수를 $K$개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.      제한 사항      풀이문제를 요약하면, N개의 수가 주어질 때, K개 이하로 중복을 허용하는 가장 긴 부분 수열의 길이를 구하는 것이다. 해당 문제의 부분 수열은 연속적이어야 하기 때문에 deque를 사용하여 앞, 뒤를 붙이거나 제거하며 풀어나가면 된다.예를 들면, $K = 2$인 상..

문제 설명N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.      제한 사항      풀이문제를 요약하면, N*N 배열에서 N번째 큰 수를 찾아내는 것이다.이때, 배열의 수는 자신의 위칸보다는 큰 수가 저장된다는 규칙이 있다. 해당 문제의 풀이는 다양하다.우선, 간단한 풀이는 N*N개의 수를 입력받아 정렬한 뒤 N번째 큰 수를 찾는 것이다.vector Nums(N*N, 0);for (int i = 0; i > Nums[i];}sort(Nums.begin(), Nums.end(), great..

문제 설명N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.지붕의 가장자리는 땅에 닿아야 한다.비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 ..

문제 설명한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.이 편집기가 지원하는 명령어는 다음과 같다.L커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)D커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)B커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨)삭제로..

문제 설명종운이는 운영하던 게임에 랭킹전 기능을 추가하려고 한다. 플레이어 간의 실력차이가 있을 수 있기 때문에 입장을 신청하면 자신과 비슷한 레벨의 플레이어들을 매칭하여 게임을 시작하게 하려고 한다.플레이어 간 매칭을 해주는 시스템은 다음과 같다.플레이어가 입장을 신청하였을 때 매칭이 가능한 방이 없다면 새로운 방을 생성하고 입장시킨다. 이떄 해당 방에는 처음 입장한 플레이어의 레벨을 기준으로 -10부터 +10까지 입장 가능하다.입장 가능한 방이 있다면 입장시킨 후 방의 정원이 모두 찰 때까지 대기시킨다.이때 입장이 가능한 방이 여러 개라면 먼저 생성된 방에 입장한다.방의 정원이 모두 차면 게임을 시작시킨다.플레이어의 수 p, 플레이어의 닉네임 n, 플레이어의 레벨 l, 방 한개의 정원 m이 주어졌을 ..

문제 설명가희는 블로그를 운영하고 있습니다. 가희는 블로그에 글을 쓰기 위해, 메모장에 키워드를 적곤 합니다.지금까지 메모장에 써진 키워드는 모두 서로 다르며, 총 N개가 존재합니다.가희는 새로운 글을 작성할 때, 최대 10개의 키워드에 대해서 글을 작성합니다.이 키워드들 중에 메모장에 있었던 키워드는 가희가 글을 쓴 이후, 메모장에서 지워지게 됩니다.가희는 블로그에 글을 쓰고 나서, 메모장에 있는 키워드 개수가 몇 개인지 알고 싶습니다. 가희를 도와주세요.      제한 사항      풀이문제를 요약하면, 미리 작성한 키워드가 있고 블로그에 글을 쓰면서 미리 작성한 키워드가 있다면 해당 키워드를 삭제한다.모든 글을 작성한 이후 남아있는 키워드에 개수를 출력해야 한다. 문제는 간단하다.글마다 키워드를 확..

문제 설명어느 날, 타노스는 0과 1로 이루어진 문자열 S$S$를 보았다. 신기하게도, S$S$가 포함하는 0의 개수와 S$S$가 포함하는 1의 개수는 모두 짝수라고 한다.갑자기 심술이 난 타노스는 S$S$를 구성하는 문자 중 절반의 0과 절반의 1을 제거하여 새로운 문자열 S′$S'$를 만들고자 한다. S′$S'$로 가능한 문자열 중 사전순으로 가장 빠른 것을 구하시오.https://www.acmicpc.net/problem/20310      제한 사항      풀이문제를 요약하면, 1과 0으로 이루어진 문자열이 주어지면 1과 0을 정확히 절반으로 줄여 만들 수 있는 문자열 중 사전순으로 가장 빠른 문자열을 만드는 것이다.1과 0이 모두 짝수로 주어지기 때문에 예외는 생각할 필요가 없다. 사전순으로 ..

문제 설명당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.) 당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다. 점..