[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시간 이상일 때 출발하..
[Codeforces 1073C] Vasya and Robot - 1800 문제 설명 : 상하좌우(U,D,L,R)로 움직일 수 있는 로봇이 있다. 이 로봇은 처음에 (0,0)부터 출발하여 목표지점 (x,y)까지 이동하고자 한다. 로봇이 어떻게 움직일지는 입력에서 (U,D,L,R)로 이루어진 문자열로 주어진다. 이 문자열대로 움직였을 때 목표지점에 도착하지 못할 수도 있다. 그래서 그 문자열의 이동 명령을 0번 이상 임의로 변경할 수가 있다. 여기서 목표 지점까지 도달하기 위해서 문자열을 변경할 때, 가장 처음 변경된 인덱스와 가장 끝에 변경된 인덱스의 거리차이를 최소화하는 문제이다. 풀이 : 일단 어떻게 변경하더라도 절대로 불가능한 경우가 있다. abs(x) + abs(y) 가 문자열의 길이(n)보다 크..
[Codeforces 1041D] Glider - 1700 문제 설명 : 높이가 h인 공중에서 글라이더를 날린다. 글라이더를 날려 보내기 시작하는 지점은 상관없다. 기본적으로 글라이더는 낙하하면서 고도가 1미터 낮아질 때마다 앞으로 1미터씩 비행하는데, 상승기류가 존재하는 구간이 있어서 그 구간에서는 글라이더의 고도가 낮아지지 않으면서 앞으로 1미터씩 비행한다. 이때 글라이더가 비행을 시작한 시점부터 땅에 닿기까지 최대로 비행할 수 있는 거리를 구하는 문제이다. 풀이 :두 가지 풀이가 있는데 하나는 이분탐색, 다른 하나는 투포인터이다. 처음에 내가 떠올린 풀이는 투포인터였는데 구현이 꼬여서 우선 이분탐색으로 푼 다음에 다시 투포인터로 풀었다. 문제에서 글라이더의 고도가 0이 되기 전까지는 계속 1미터씩 ..
[Codeforces 1138C] Skyscrapers 문제 설명 :(n x m)크기의 행렬이 주어진다. 이 행렬에서 각각의 원소는 문제에서 정의한 연산에 의해서 어떤 값으로 바꿀 수 있다. 그 연산이란 어떤 원소와 그 원소가 속한 열과 행에 있는 모든 원소와 상대적인 크기(크거나, 작거나, 같거나)를 매겨서 이 관계가 유지되는 한에서 원소의 값을 조절할 수 있다. 그래서 이 과정을 거치면서 각 행과 열에 포함된 원소의 값 중에서 가장 큰 값이 최소가 되도록 만드는 문제이다. 풀이 : 각 행과 열에 포함된 원소의 값중에서 최대값이 최소가 되도록 만들어야 하므로, 각 값들 간의 차이는 1이 되도록 해야 한다. 그러면서 어떤 원소의 값의 최소를 구하기 위해서는 그 값보다 작은 원소의 개수가 몇 개인지 카운트..