[Codeforces 1025C] Plasticine zebra - 1600 문제 설명 : 문자열에서 특정 연산이 하나 정의된다. 그 연산은 문자열 내에서 특정 인덱스 사이를 기준으로 양 옆의 문자열을 reverse하는 연산이다. 이 연산을 0번 이상 사용하여 나온 문자열에서 b,w가 교대로 최대 몇 번 등장할 수 있는지를 구하는 문제이다. 풀이 : 결과적으로 '특정 연산'을 사용하게 되면 그 결과는 원본 문자열에서 몇 번 만큼 shift한 결과와 동일하다. 아직까지는 왜 이것이 가능한지는 밝히지 못했다. 따라서 나는 원본 문자열을 특정 횟수만큼 shift했을 때 최대 몇 번 b,w가 교대로 등장하는지만 세주면 된다. 이에 대한 구현은 원본 문자열 뒤에 똑같이 문자열을 붙여면 O(N)만에 수행할 수 있다..
[Codeforces 1081D] Maximum Distance -1800 문제 설명 : n개의 vertex와 그 중에서 k개의 special vertex를 가지는 그래프가 주어진다. 문제는 각 special vertex간의 최장거리를 구하면 되는데, 이 문제 내에서 정의하는 '거리'란 edge들의 가중치의 합이 아닌 edge들의 가중치 중에서 가장 큰 값을 거리라고 정의한다. 예를 들어서 1->2로 가는데 가중치가 10, 2->3으로 가는데 가중치가 20이라면 1->3으로 가는 거리는 30이 아닌 20이 되는 것이다. 풀이 : 이 문제는 MST(minimum spanning tree)로 풀면 된다. 즉 edge의 가중치를 오름차순으로 정렬한 뒤, special vertex가 모두 connected될 때..
[Codeforces 1034A] Enlarge GCD - 1700 문제 설명 : n개의 숫자가 주어진다. 이 중에서 숫자 k 개를 삭제한 뒤 나머지 (n-k)개 수들의 GCD(최대공약수)가 삭제하기 이전의 GCD보다 크도록 만들어야 한다. 그러기 위해서는 최소 몇 개의 숫자를 삭제해야 하는지 구하는 문제이다(= 가장 작은 k값을 구하여라). 풀이 : 먼저 N개 수들의 GCD를 먼저 구한 뒤, 다시 모든 수들을 GCD로 나눠준다. 나눠진 수들의 GCD는 당연히 1이다. 이 숫자들을 각각 소인수분해하여 가장 많이 등장하는 소인수의 횟수를 N에서 빼주면 된다. 가장 많이 등장하는 소인수를 포함하지 않은 수들을 모두 삭제하고 나면, 그 소인수를 GCD로 취할 수 있기 때문이다. 그리고 이 문제에서 중요한 is..
[Codefocres 1061C] Multiplicity - 1700 문제 설명 : 어떤 집합의 원소 N개가 주어진다. 그 집합에서 부분집합(subset)을 만들 건데 부분집합의 원소의 개수는 1개 이상이여야 하고 i번 째 원소는 반드시 i로 나누어 떨어져야 한다. 이 두 조건을 만족하는 부분집합을 만들 수 있는 경우의 수를 구하는 문제이다. 풀이 : 메모리 초과, 시간 초과와 싸워야 하는 문제이다.각 원소가 1~N 사이의 정수 j로 나누어 떨어지는지 확인한다. 나누어 떨어진다면 그 원소는 subset의 j번째 원소가 될 자격이 있는 것이다. 이를 만약 현재 보고 있는 원소가 j로 나누어 떨어진다면 그 경우의 수를 2차원 dp로 나타내면 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]이..
[Codeforces 1041D] Glider - 1700 문제 설명 : 높이가 h인 공중에서 글라이더를 날린다. 글라이더를 날려 보내기 시작하는 지점은 상관없다. 기본적으로 글라이더는 낙하하면서 고도가 1미터 낮아질 때마다 앞으로 1미터씩 비행하는데, 상승기류가 존재하는 구간이 있어서 그 구간에서는 글라이더의 고도가 낮아지지 않으면서 앞으로 1미터씩 비행한다. 이때 글라이더가 비행을 시작한 시점부터 땅에 닿기까지 최대로 비행할 수 있는 거리를 구하는 문제이다. 풀이 :두 가지 풀이가 있는데 하나는 이분탐색, 다른 하나는 투포인터이다. 처음에 내가 떠올린 풀이는 투포인터였는데 구현이 꼬여서 우선 이분탐색으로 푼 다음에 다시 투포인터로 풀었다. 문제에서 글라이더의 고도가 0이 되기 전까지는 계속 1미터씩 ..
[Codeforces 1036D] Vasya and Arrays 문제 설명 : 배열 A와 B가 주어진다. 이 배열에서는 특수한 연산이 정의되어 있는데 그 연산은 배열 내에서 연속한 원소들을 더해서 하나의 원소로 압축할 수 있다. 이 연산을 사용해서 A와 B의 모든 원소들이 일치하도록 만들 수 있는 최대 길이를 구하는 문제이다. 풀이 :문제의 풀이 자체는 금방 떠올랐다. A배열과 B배열에서 각각 원소들을 차례로 더해나간다. 만약 A의 합 더 크면 B의 원소에서 더하고, B의 합이 더 크면 A의 원소를 더하는 방식으로 A와 B의 합이 같아질 때까지 더해나간다. 그래서 현재 더해야 할 원소의 인덱스를 가리키는 a,b변수가 있다. 이렇게 끝까지 갔을 때, 같아진 적이 총 몇 번인지 세면 된다. 주의할 점 : 문..
[Codeforces 1084D] The Fair Nut and the Best Path 문제 설명 : n개의 노드가 있는 트리가 있다. 각 노드에는 양의 가중치가 있으며, 노드 간의 간선에도 가중치가 있다. 노드를 지날 때는 그 노드에 배정된 가중치 만큼 값을 더할 수 있으며, 간선을 지날 때에는 그 간선에 배정된 가중치 만큼 가중치가 차감된다. 이때 얻을 수 있는 최대의 가중치의 합을 구하는 문제이다. 각 노드는 단 한번만 방문이 가능하며, 시작 지점은 어디든 상관없다. 풀이 : 이 문제에서의 가장 중요한 이슈는 트리를 순회하면서 앞으로 갈 노드(next)를 방문하는 것이 이득일지 아닐지에 대한 문제이다. 이를 구하는 함수가 dfs(next)인데, 이 dfs(next)의 반환값이 양수라면 방문하는 것..
[Codeforces 1096D] Easy Problem 문제 설명 : 알파벳 소문자로 이루어진 문자열이 주어진다. 이 문자열에서 최소 0개이상의 문자들을 삭제해야 하는데 그 조건은 그 문자열에서 순서대로 "h,a,r,d"가 나타나지 않도록 하는 것이다(떨어져 있을 수도 있다). 각 문자에는 가중치(ambiguity)가 존재하여 가중치의 합이 최소가 되도록 제거해야 한다. 풀이 : 처음에는 그리디로 풀려고 했는데 안되고, dp로 풀어야 하는 문제이다.전체 문자열(str)을 살피면서 "h,a,r,d"로 하나씩 매칭해본다.만약 현재 문자 str[i]와 패턴 ptn[j]가 일치한다면 내가 할 수 있는 선택은 두 가지이다. 1. 현재 ptn(패턴)을 삭제하기로 결정한다. 이 경우의 현재 위치의 ambiguity..