https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 앞서 푼 문제와 유사한 느낌이다. 이 문제는 문제의 세부사항을 자세히 읽어줘야 한다. 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이를 구한다. 어떤 문자를 정확히 K개를 포함하고, 문자열의 첫 번째와 마지막 글자가 해당 문자로 같은 가장 긴 연속 문자열의 길이를 구한다. 정확히 어떤 특정 문자를 K개를 포함해야하므로 문자별로 존재하는 인덱스의 배열(a ~ z)을 각각 탐색한..

https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 어렵게만 생각했는데 슬라이딩 윈도우를 잘 적용하면 문제가 훨씬 쉬워진다. a와 b를 분리하는 것이므로 a의 개수를 센 뒤, 윈도우 크기를 설정한다. 그리고 윈도우를 한 칸씩 움직여보면서 해당 윈도우에 b의 개수를 최소인 경우를 찾아낸다. #include #include using namespace std; int s, e; int main(void) { string str; cin >> str; in..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 이해를 포기할 수 밖에 없는 어려운 구현 문제이다. 크게 단계를 잘 쪼개야 한다. 1. 컨베이어 벨트를 돌린다(로봇과 별개) 2. 로봇을 한 칸씩 앞으로 이동 - 그 과정에서 내리는 칸에 있는 건 다 버리기 3. 로봇 추가 그리고 내구도는 로봇이 빠진다고 해서 다시 올라오지 않는다. #include #include #define MAX 220 using namespace st..

https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 해시를 이용할 때 ordered_set이 아니라 unordered_set을 이용해야 한다. unorded_set은 set과 다르게 정렬되지 않으며 해시 함수를 이용해 원소를 탐색한다. Set은 정렬되어있는 상태에서 탐색을 하므로 $O(log N)$ 시간이 걸린다. 평균도 최악도! Hash Set은 해시 함수로 탐색을 하므로 평균 $O(1)$ 상수 시간이 걸려 빠르..

https://www.acmicpc.net/problem/7573 7573번: 고기잡이 한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고 www.acmicpc.net 앞서 풀었던 하늘에서 별똥별이 빗발친다 문제의 연습을 하기 위해 비슷한 유형으로 풀어보았다. 이 문제 역시도 모서리에 물고기를 걸쳐 고기잡이 배를 만든다. 대신 그물의 폭만 만들어져 있어서 가로, 세로로 늘리고 줄여서 모두 도전해보면 된다. #include #include using namespace std; struct Net { int x, y; }; int N, I, M, res; vector arr; ..

https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제의 조건이 상당히 중요하다. 별똥별의 위치를 나타내는 좌표의 범위가 상당히 크다.(가로, 세로로 각각 50만..) 따라서 애초에 해당 좌표를 표시하는 2차원 배열을 쓸 생각을 버리고 시작해야 한다. 대신 별똥별의 개수가 최대 100개로 크지 않다. 따라서 별똥별을 일반 벡터에 있는 것으로 처리한다. 여기까지는 잘 풀었..