[CF 1684C]Column Swapping - 1400 문제 설명 n개의 행과 m개의 열이 있으며 모든 값이 양의 정수인 격자가 주어진다. 이때 임의의 2개의 열의 위치(동일 위치끼리도 가능)를 서로 바꾸어 모든 행이 오름차순으로 정렬된 상태에 놓이게 만들 수 있는가? 만약 그렇다면 위치를 서로 교환할 2개의 열의 인덱스를 출력하고 그렇지 않으면 -1을 출력하라. 문제 풀이 문제를 단순화시켜서, 열이 1개짜리인 1xm 짜리 행렬(수열)이라고 가정해보자. 이 수열이 정확히 1번의 swap연산을 통해서 $a_i
[CF 1667A] Make it Increasing - 1300 Problem - A - Codeforces codeforces.com 문제 설명 길이가 n인 배열 a가 주어지고, 모든 원소가 0인 길이가 n인 배열 b가 있다. 이때 $b_{i}$에서 $a_{i}$를 원하는 만큼 더하거나 빼는 연산을 할 수 있다. 배열 b를 중복 없이 증가하는 수열로 만들고자 할 때 필요한 최소 연산의 수를 구하시오. 문제 풀이 N의 크기가 5000밖에 되지 않기 때문에 $N^2$풀이를 생각해볼 수 있다. $N^2$이라면 고정된 i에 대한 최솟값을 $N$만에 구하고, i를 [1, N]에 대해 다 돌려보면 된다. 고정된 i의 위치의 값은 0이고, 그 양 옆 범위인 [1,i-1], [i+1,N]의 범위만 조작하면 된다. ..
[CF 1136D] Nastya Is Buying Lunch - 1800 문제 설명 : n명이 줄을 서 있고 문제의 주인공은 줄의 맨 뒤(n번째 인덱스)에 서 있다. 그리고 m개의 정보가 들어오는데 각 정보는 두 정수 a,b로 이루어져있다. 이 의미는 줄의 앞사람이 a번 사람이고 뒷사람이 b번 사람이라면 a와 b가 서로 자리를 바꿀 수 있다는 의미이다. 이 정보들을 바탕으로 n번째 사람은 최대 몇 칸이나 앞으로 움직일 수 있는지 구하는 문제이다. 풀이 : 이 문제에서 관심이 있는 것은 맨 뒷사람(편의상 last라고 두자)이 최대 몇 칸이나 앞으로 움직일 수 있는지를 구하는 문제이다. 따라서 정보들 중에서 내가 관심있게 보는 것은 ( ? , last )라는 정보가 중요하지만 동시에 ? 직전까지 움직일수 있..
[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 1153C] Serval and Parenthesis Sequence - 1600 문제 설명 : (,),? 로 이루어진 문자열이 주어진다. 이 중에서 ?로 채워진 칸은 임의로 ( 또는 ) 로 바꿀 수 있다. 이때 strict prefix(길이가 0이거나 n일 때는 제외하는 prefix)는 절대로 올바른 괄호열이 되어서는 안되게하면서, 전체 문자열은 반드시 올바른 괄호열이 되어야 한다. 이 두 조건은 만족하는 문자열을 구하는 문제이다. 풀이 : 처음에는 엄청나게 오답을 꼬라박은 문제이다. 처음 풀이는 여는 괄호 '(' 을 +1, 닫는 괄호 ')'를 -1, 이것들의 누적합을 sum이라고 했을 때 sum이 1이나 2 사이에서만 움직이도록 통제하였다. 하지만 이 풀이는 " ???))) "같..
[Codeforces 950C] Zebras - 1600 문제 설명 : 문제에서 'zebra'라는 특정 문자열을 정의해주는데 이 문자열은 시작과 끝은 반드시 '0'이어야하고, 0과 1이 번갈아가면서 나타나야한다. 그래서 0과 1로만 이루어진 문자열이 주어졌을 때 이 문자열을 적당히 분할하여 모든 substring을 'zebra' 문자열의 조건을 만족시킬 수 있는지 찾는 문제이다. 풀이 : 0 뒤에는 가장 가까운 1을 찾고, 1 뒤에는 가장 가까운 0을 찾는 방식으로 풀면 된다. 이때 substring의 시작과 끝은 반드시 0이어야하므로, 1로만 시작되거나 1로 끝나는 substring이 발견되었을 때는 불가능처리를 한다. 처음에 이 풀이에 대한 구현을 현재 문자에대한 다음(find)문자를 문자열 끝까지 ..
[Codeforces 1036D] Vasya and Arrays 문제 설명 : 배열 A와 B가 주어진다. 이 배열에서는 특수한 연산이 정의되어 있는데 그 연산은 배열 내에서 연속한 원소들을 더해서 하나의 원소로 압축할 수 있다. 이 연산을 사용해서 A와 B의 모든 원소들이 일치하도록 만들 수 있는 최대 길이를 구하는 문제이다. 풀이 :문제의 풀이 자체는 금방 떠올랐다. A배열과 B배열에서 각각 원소들을 차례로 더해나간다. 만약 A의 합 더 크면 B의 원소에서 더하고, B의 합이 더 크면 A의 원소를 더하는 방식으로 A와 B의 합이 같아질 때까지 더해나간다. 그래서 현재 더해야 할 원소의 인덱스를 가리키는 a,b변수가 있다. 이렇게 끝까지 갔을 때, 같아진 적이 총 몇 번인지 세면 된다. 주의할 점 : 문..
[Codeforces 1066B] Heaters 역시나 전형적인 그리디 문제이다. 처음에 풀 때는 문제 조건을 잘못 이해해서 한참 고생했다. '1'은 히터가 존재하는 위치일 뿐 전원은 꺼져있다고 간주해야하는데 나는 전원이 켜져있다고 생각해서 실제 정답보다 답을 적게 구했다.풀이는 간단하다. 왼쪽에서부터 오른쪽으로 가면서 현재 위치(cur)에서 가장 오른쪽에 있는 히터를 발견하면, 그 지점(i)을 기준으로 [i-r+1,i+r-1]은 heating할 수 있다는 의미이다. 그래서 나는 그 히터의 범위가 닿지 않기 시작하는 위치(=i+r)로 cur를 바꿔주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454..