전체 글

문제 설명2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?      제한 사항      풀이문제를 요약하면, 2차원의 블록의 높이에 대한 입력이 주어지면 그 블록들 사이에 고이는 물의 양을 구하는 것이다.예를 들어,검은색은 블록을 나타내며 하늘색은 물을 나타낸다.위의 경우 고이는 물의 양은 5이다. 해당 문제를 해결하는 방법은 간단하다.물은 왼쪽에서 가장 높은 블록과 오른쪽에서 가장 높은 블록 중 낮은 높이에 맞춰 고이게 된다.1번 기둥(높이:1)의 경우, 왼쪽은 0번 기둥(높이:3)이 가장 높고 오른쪽은 4번 기둥(높이:4)이 가장 높은기둥이다.이 중, 낮은 기둥인 0번 기둥의 높이에서 자신의 높이의 차이로 물이 고이게 된다...

문제 설명KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높..

문제 설명작년에 이어 새로운 문자열 게임이 있다. 게임의 진행 방식은 아래와 같다.알파벳 소문자로 이루어진 문자열 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..

문제 설명수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/13549      제한 사항      풀이문제를 요약하면, N에서 K로 이동할 때, 가장 짧은 이동 시간을 구하는 것이다.N에서 K로 이동하는 방법은 걸어가면 1초를..

문제 설명빨간색 볼과 파란색 볼이 에서 보인 것처럼 일직선상에 섞여 놓여 있을 때, 볼을 옮겨서 같은 색 볼끼리 인접하게 놓이도록 하려고 한다. 볼을 옮기는 규칙은 다음과 같다.바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘어 옮길 수 있다. 즉, 빨간색 볼은 옆에 있는 파란색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다. 유사하게, 파란색 볼은 옆에 있는 빨간색 볼 무더기를 한 번에 뛰어 넘어 옮길 수 있다.옮길 수 있는 볼의 색깔은 한 가지이다. 즉, 빨간색 볼을 처음에 옮겼으면 다음에도 빨간색 볼만 옮길 수 있다. 유사하게, 파란색 볼을 처음에 옮겼으면 다음에도 파란색 볼만 옮길 수 있다.예를 들어, 처음에 볼이 에서 보인 것처럼 있을 때, 빨간 볼을 에서 보인 것처럼 옮긴 후, 에서 ..

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