전체 글

문제 설명가희는 블로그를 운영하고 있습니다. 가희는 블로그에 글을 쓰기 위해, 메모장에 키워드를 적곤 합니다.지금까지 메모장에 써진 키워드는 모두 서로 다르며, 총 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 X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다.2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필..

문제 설명찬솔이는 블로그를 시작한 지 벌써 $N$일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 $X$일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 $X$일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.      제한 사항      풀이문제를 요약하면, X일 동안 최다 방문자 수를 구하는 것이다.또한, 최다 방문자 수의 구간의 개수도 같이 구해야 한다. 해당 문제는 누적합을 이용하면 간단하게 해결할 수 있다.누적합을 이용하면 i일부터 i+X-1일까지의 합을 $O(1)$시간 안에 구할 수 있다.예를 들어, 2일 부터 3일까지의 누적합을 계산하는 경우를 봐보자.2~3일의 방문자 수는 6이 된다...

문제 설명크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다. 한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 합하여 계산한다. 점수는 자격을 갖춘 팀의 주자들에게만 주어지며, 결승점을 통과한 순서대로 점수를 받는다. 이 점수를 더하여 가장 낮은 점수를 얻는 팀이 우승을 하게 된다. 여섯 명의 주자가 참가하지 못한 팀은 점수 계산에서 제외된다. 동점의 경우에는 다섯 번째 주자가 가장 빨리 들어온 팀이 우승하게 된다.예를 들어, 다음..