문제 설명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 이다. 점..
문제 설명영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.두 개의 단어가 같은 종류의 문자로 이루어져 있다.같은 문자는 같은 개수 만큼 있다.예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비..
문제 설명찬솔이는 블로그를 시작한 지 벌써 $N$일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 $X$일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 $X$일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. 제한 사항 풀이문제를 요약하면, X일 동안 최다 방문자 수를 구하는 것이다.또한, 최다 방문자 수의 구간의 개수도 같이 구해야 한다. 해당 문제는 누적합을 이용하면 간단하게 해결할 수 있다.누적합을 이용하면 i일부터 i+X-1일까지의 합을 $O(1)$시간 안에 구할 수 있다.예를 들어, 2일 부터 3일까지의 누적합을 계산하는 경우를 봐보자.2~3일의 방문자 수는 6이 된다...
문제 설명크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다. 한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 합하여 계산한다. 점수는 자격을 갖춘 팀의 주자들에게만 주어지며, 결승점을 통과한 순서대로 점수를 받는다. 이 점수를 더하여 가장 낮은 점수를 얻는 팀이 우승을 하게 된다. 여섯 명의 주자가 참가하지 못한 팀은 점수 계산에서 제외된다. 동점의 경우에는 다섯 번째 주자가 가장 빨리 들어온 팀이 우승하게 된다.예를 들어, 다음..
