mojo's Blog

문제 링크 : Problem - C - Codeforces Problem - C - Codeforces codeforces.com Vadim loves decorating the Christmas tree, so he got a beautiful garland as a present. It consists of nn light bulbs in a single row. Each bulb has a number from 1 to n (in arbitrary order), such that all the numbers are distinct. While Vadim was solving problems, his home Carp removed some light bulbs from the garland. Now..

문제 링크 : Problem - C - Codeforces Problem - C - Codeforces codeforces.com 그리디 + 바이너리 서칭 문제이다. 문제를 요약하면 인풋으로 받은 배열 A = [\(a_{1}\), ... , \(a_{n}\)] 에 대해서 \(a_{i}\) := \(a_{i}\) mod x (i ≠ x) 와 같은 작업을 수행함으로써 만들어진 배열이 1에서 n까지의 permutation 배열을 만들도록 하는 것이다. permutation 배열은 예를 들어서 [1, 2, 3, 4], [1, 3, 2, 4], [3, 2, 1, 4], ... 등 다양하다. 이에 대한 성질을 생각해보면 1에서 n까지의 자연수가 각각 한 개씩 존재하도록 위와 같은 작업을 하면 된다. 즉, 문제에서 ..

문제 링크 : Problem - C - Codeforces Problem - C - Codeforces codeforces.com 이진탐색 + 그리디 문제이다. 옮길 수 있는 최소 돌 x에 대하여 해당 돌이 문제에서 주어진 작업에 해당하면서 n 부터 3 까지 돌을 이동시키면서 마지막에 놓여진 1, 2 번째 돌의 갯수가 x 이상일 경우를 살피는 문제이다. 이러한 최소 돌 x를 바이너리 서칭을 함으로써 최대로 얻을 수 있는 x를 찾고 해당 답이 정답이 된다. 핵심이 되는 부분 : check 하는 과정에서 돌을 옮길 수 d 에 대하여 d = min(h[i], cur_h[i] - x) / 3 를 잡는 점이다. 돌을 옮기는 수(d)를 구하는 과정에서 이동할 수 있는 돌의 수(cur_h[i] - x)가 기존에 있던..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com 완전 탐색 + 구현 문제이다. 어제 서강대 학회분들과 함께 풀다가 뇌절을 한 문제이다. (9번 트라이 실패) 문자열 S의 [i, j] 범위의 서브문자열을 S(i, j) 라고 할 때 다음 세가지 조건을 만족해야 한다. ① 적어도 길이가 2여야 한다 => Len(S(i, j)) ≥ 2 ② 'a'의 갯수는 'b'의 갯수보다 커야 한다 => a_size(S(i, j)) > b_size(S(i, j)) ③ 'a'의 갯수는 'c'의 갯수보다 커야 한다 => a_size(S(i, j)) > c_size(S(i, j)) 문제 자체는 어렵지 않다. s[i] = 'a', s[j] = 'a' ..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com Topological Sorting 과 dynamic programming 의 짬뽕 문제이다. 백준에서만 풀었던 위상정렬을 여기서 풀게되서 뭔가 감회가 새로웠다. 문제는 x 번째 책을 읽기 위해서 미리 읽어야 할 책들의 list 가 n개 주어진다. 이때, 책을 모두 읽기 위해 걸리는 시간을 구해야 한다. 읽어야 할 책 : x, 미리 읽어야 할 책 : y 라고 할 때 x의 진입차수를 높여주고 단방향으로 y => x 를 이어주도록 한다. 그렇게 모든 세팅이 끝나면 모든 책들이 읽힐 수 있는지 확인하는 과정을 거친다. 즉, 진입차수가 0인 책들을 발견해가면서 모든 책을 읽을 수 ..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com 홀수로 구성된 배열 A와 짝수로 구성된 배열 B가 존재할 때, A[0] < B[0] 을 만족하도록 swap이 이루어진 갯수의 최솟값을 구하는 문제이다. 문제 접근 방법은 다음과 같다. 1. 배열 A의 원소 x에 대하여 m[x] = i 라고 설정함 ex ) A = [1, 3, 5, 7, 9] 에 대하여 각각 맨 앞에 숫자를 배치하도록 하기 위해 0, 1, 2, 3, 4 만큼 이동 2. 배열 B의 원소 x와 인덱스 i에 대하여 (x, i) 값을 담을 수 있는 벡터 v에 대하여 v.push_back({x, i}), check[i] = 1 라고 설정한 후에 x를 기준으로 오름차순으..