[CF 1114D] Flood Fill - 1900 문제 설명 : n개의 수가 주어지고 이 중에서 시작할 수 1개를 고른다. 그리고 매 시행마다 시작 위치가 포함된 똑같은 수로 연결된 한 덩어리를 다른 숫자로 바꿀 수 있다. 이때 모든 숫자를 똑같은 숫자로 바꾸는데 필요한 최소 시행 수를 구하여라. 풀이 : 우선 맨 처음에 n개의 수를 입력받으면 unique연산을 취해서 인접해 있으면서 값이 같은 수를 미리 없애준다. 인접한 같은 수는 어차피 한 덩어리이므로 정답에 영향이 없기 때문이다. unique를 취한 후에는 인접한 숫자끼리는 모두 다를 것이라는 확신을 할 수가 있다. 그러고 난 뒤에 각 시행에서 내가 신경써야할 것은 시행의 가장 왼쪽 수(l)와 가장 오른쪽 수(r)가 같은지 여부이다. 만약에 같다..
[CF 828C] String Reconstruction - 1700 문제 설명 : n개의 부분문자열(substring)과 이 부분문자열이 전체 문자열에서 등장하는 시작 위치가 주어진다. 이 부분문자열의 정보를 바탕으로 전체 문자열을 구성할 때, 사전순으로 가장 앞서도록 만드는 문제이다. (입력되는 정보는 모순되지 않는다) 풀이 : 입력되는 정보는 모순되지 않으므로 단순하게 substring을 i번째 위치에 넣는다고 생각하면 된다. 하지만 naive하게 생각해서 k_i개의 위치에 대해서 substring의 모든 글자를 다 비교해보면 시간초과가 난다. 예를 들어 substring이 "aaa...aa"로 총 100만 글자이고, k_i=100만개 : {1,2,3,...100만}이라면 시간복잡도는 100만 * ..
[CF 1136D] Nastya Is Buying Lunch - 1800 문제 설명 : n명이 줄을 서 있고 문제의 주인공은 줄의 맨 뒤(n번째 인덱스)에 서 있다. 그리고 m개의 정보가 들어오는데 각 정보는 두 정수 a,b로 이루어져있다. 이 의미는 줄의 앞사람이 a번 사람이고 뒷사람이 b번 사람이라면 a와 b가 서로 자리를 바꿀 수 있다는 의미이다. 이 정보들을 바탕으로 n번째 사람은 최대 몇 칸이나 앞으로 움직일 수 있는지 구하는 문제이다. 풀이 : 이 문제에서 관심이 있는 것은 맨 뒷사람(편의상 last라고 두자)이 최대 몇 칸이나 앞으로 움직일 수 있는지를 구하는 문제이다. 따라서 정보들 중에서 내가 관심있게 보는 것은 ( ? , last )라는 정보가 중요하지만 동시에 ? 직전까지 움직일수 있..
[CF 1118F1] Tree Cutting (Easy Version) - 1800 문제 설명 : 빨간색,파란색,무색(색깔 없음)노드로 이루어진 트리가 주어진다. 트리의 간선 (n-1)개 중에서 어느 한 간선을 제거했을 때 만들어지는 2개의 component가 있을텐데, 각 component를 이루는 노드의 색깔이 빨간색과 파란색이 동시에 존재하지 않도록 하는 간선이 몇 개인지 구하는 문제이다. 풀이 : 처음 생각한 것은 각 간선별로 하나씩 지워보고 만들어지는 2개의 component의 노드 색깔을 조사해볼까 생각해봤는데, 노드 수(간선 수)가 최대 30만이므로 이 풀이로는 힘들 것 같았다. 그래서 어떻게든 한 번의 순회만으로 제거할 수 있는 간선을 찾는 것이 유력하다고 생각했다. 정답을 만족시키는 두 ..
[CF 1169B] Pairs - 1500 문제 설명 : 두 개의 정수로 구성된 pair가 총 m개 주어진다. 임의의 정수 2개(x,y)를 선택해서 최소 하나의 정수가 모든 pair에 등장하게 만들 수 있는지 판단하는 문제이다. 풀이 : 정답이 존재하기 위해서는 m개의 pair중에서 임의의 pair 하나를 선택했을 때 둘 중 하나는 반드시 x,y와 동일할 것이다. 그래서 기본 전제로 pair의 0번째 원소(몇 번째 원소인지는 상관없다) 중 하나에 x,y중 하나는 존재한다는 것을 깔아서 이것이 성립할 수 있는지 검증해볼 것이다. pair의 첫 번째 원소의 first와 second를 각각 x라고 가정하고, 다음과 같은 시행을 한다 : m개의 pair에 대해서 두 정수 모두 x와 같지 않다면 need라는 변수..
[CF 898D] Alarm Clock - 1700 문제 설명 : n개의 알람이 울리는 시간이 주어진다. 알람이 연속된 m분의 시간동안 k개 이상 울려서는 안된다. 이 조건을 만족시키기 위해서 꺼야하는 알람의 최소 개수를 구하여라. 풀이 : 선택한 구간에서 가장 작은 시간을 t_s라고 한다면 [t_s , t_s+m)구간에 포함되는 시간이 k개 미만이어야 한다. 이를 구현하기 위해서 자료구조 deque를 사용할 것이다. 우선 알람 시각들을 오름차순으로 정렬한다. 그 다음 시각들을 훑으면서 deque에 push_back한다. 그러면 deque의 front에는 먼저 들어간 시각이 들어 있으므로 작은 수가, back에는 나중에 들어간 시각이므로 큰 수가 들어있게 된다. 그래서 back-front의 값이 m보다 ..
[Codeforces 1148B] Born This Way - 1700 문제 설명 : A~B, B~C로 가는 비행기 시간표가 있다. 여기서 최대 k개의 비행기편을 취소시켜서 C에 도착하는 시간을 최대한 늦추어야 한다. A~B 소요시간은 ab, B~C 소요시간은 bc이며, 경우에 따라 C에 도착하는 경우가 불가능하게 만들 수도 있다. 풀이 :경우의 수로 문제를 쪼개서 풀 수 있는 유형이다(이 문제 풀이의 핵심). 총 k개의 항공편을 취소할 수 있으므로 1를 A~B, B~C로 적절하게 분배하여 최대한으로 늦추는 경우를 찾으면 된다. 그래서 A~B 0개 B~C k개, A~B 1개 B~C k-1개....이런 식으로 모든 경우를 조사해 보는 것이 다. 그래서 B에 도착한 시간이 t이라면, t시간 이상일 때 출발하..