[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..
[Codeforces 1070H] BerOS File Suggestion - 1600 문제 설명 : 처음에 n개의 파일이름(문자열)이 주어진다. 그 다음 q개의 쿼리가 들어오는데, 각 쿼리는 substring을 제시하여 n개의 파일 중에서 해당 substring 포함하는 파일은 총 몇 개인지와 존재한다면 아무 파일이름을 출력하면 된다. 풀이 : 정말 고민을 많이 했던 문제이다. 일단 n이 1만, q가 5만이기 때문에 각 쿼리마다 모든 n을 살펴보는 것은 시간이 초과된다( O(n*q) ). 따라서 반드시 전처리과정을 거친 뒤에야 쿼리를 받을 때 빠르게 답을 출력하는 형태가 될 것이라고 짐작했다. 실제로 솔루션은 한 문자열에서 나올 수 있는 모든 substring의 경우의 수를 map에다 저장해서 카운트 해..
[Codeforces 1082D] Maximum Diameter Graph 문제 설명 : n개의 vertex에 대해서 각 vertex당 최대로 연결 가능한 degree의 수가 주어진다. 그 degree 이내에서 만들 수 있는 그래프 중에서 지름의 길이가 가장 길도록 그래프를 만들 때, 지름의 길이와 그 때의 간선 연결 관계를 출력하는 문제이다. 풀이 : 이 문제에서 가장 먼저 생각해야 할 점은 '지름의 길이를 최대가 되도록'해야한다. 어떻게 하면 최대가 될까? 일단 그래프를 반드시 트리의 형태로 만들어야 한다. 사이클이 생기는 그래프는 지름의 길이가 짧아질 수도 있다. 트리로 만들겠다고 방향을 잡은 뒤에 생각할 것은 vertex들을 어떻게 연결해야 지름이 가장 길어질 것인가에 대한 생각이다. degree..
[Codeforces 1062B] Math 문제 설명 : 임의의 수 n이 주어졌을 때, 두 가지 종류의 연산을 수행할 수 있다. 하나는 n에다가 임의의 수 x를 곱할 수 있고, 다른 하나는 (현재 n이 제곱수 일 때)루트를 취할 수 있다. 이 두 연산을 사용하여 n을 최대한 작게 만들고, 그 수행 횟수를 구하는 문제이다. 풀이 : 이 문제와 같이 어떤 수가 주어지고, 그 숫자에 연산을 취해서 값이 변해나가는 유형의 문제는 본인이 직접 예시 숫자들을 몇 개 끄적여보면서 규칙성(혹은 최적의 방법)을 찾아나가야 한다.n을 최대한 작게 만드는게 목표이므로 나는 루트를 최대한으로 많이 취해야 할 것이다. 따라서 루트 연산이 가능한 형태로 n을 가공해야 한다. 루트 연산은 소인수들의 지수들이 모두 짝수여야만 가능하..
[Codeforces 1080C] Masha and two friends 문제 설명 : n*m크기의 체스판이 있다. 이 체스판에 두 사람이 흰색 물감과 검정색 물감을 쏟았다. 물감이 쏟아진 모양이 직사각형일 때 쏟고난 뒤에 체스판에 칠해진 흰색 칸과 검정색 칸의 수를 구하는 문제이다. 풀이 : 처음에 풀 때는 엄청난 솔루션이 존재할 줄 알았는데, 그냥 단순 수학 문제이다. 흰색 물감이 칠해진 영역, 검정색 물감이 칠해진 영역, (만약 존재한다면) 두 물감이 겹치는 영역을 따로 구해서 전체 흰색, 검정색 수에 더하고 빼면 된다. 주의할 점 : 영역에 있는 블럭의 수가 짝수개라면 흰색과 검정색 수가 같지만, (홀수)*(홀수) 영역이라면 블럭의 수가 홀수이므로 흰색과 검정색의 수가 1개 차이나게 된다. 이 부..
[Codeforces 1144F] Graph Without Long Directed Paths Problem - F - Codeforces codeforces.com 유형 : DFS, graph 문제 설명 : 입력으로 vertex가 n개이고 u와 v를 연결하는 undirectd인 간선이 m개 주어진다. 이 간선들을 directed로 전환해서 그래프에 길이가 2이상인 경로가 없도록 만들어야 한다. 어떻게 전환해도 불가능한 경우에는 "NO"를 출력하고, 가능하다면 "YES"와 함께 입력에서 주어진 간선의 정보 (u->v)를 그대로 전환한다면 0을 출력하고, 그와 반대인 (v->u)로 전환한다면 1을 출력하는 문제이다. 풀이 : 예전에 푼 적이 있는 [Codeforces 1093D] Beautiful Grap..