mojo's Blog

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com 그래프를 이용한 문제이다. 주어진 조건으로 얻은 그래프를 통해서 무조건 한번만 마을을 방문하여 모든 마을을 방문할 수 있는지를 묻는 문제이다. 문제에서 주어진 조건을 단순하게 요약하면 다음과 같다. n(1~10000, 정수)값이 주어질 때, (1) 1 번째 마을에서 2 번째 마을로 가는 도로 존재 2 번째 마을에서 3 번째 마을로 가는 도로 존재 ... (n - 1) 번째 마을에서 n 번째 마을로 가는 도로 존재 (2) ai = 0 ) i 번째 마을에서 (n + 1) 번째 마을로 가는 도로 존재 ai = 1 ) (n + 1) 번째 마을에서 i 번째 마을로 가는 도로 존재 확..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com dp + greedy 문제이다. 이 문제는 'R', 'B' 가 최소한으로 연달아 나타나도록 '?' 문자를 'R', 'B' 둘 중에 하나를 채워 넣는 문제이다. 그래서 임의의 문자열을 s1, s2를 둬서 s1 같은 경우는 'R' => 'B' => 'R' => ... 식으로 채우도록 하고 s2 같은 경우는 s1의 문자와 반대로 'B' => 'R' => 'B' => ... 식으로 채우도록 하였다. 문제에서 제공된 문자열 하나를 살펴보도록 한다. S = "?R???BR" 가 주어졌을때, s1, s2를 채워가는 과정을 보이도록 하면 다음과 같다. S[0] = '?' => s1 = "..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com 이 문제는 그래프를 단순하게 연결하고 끊어야 할것같은 느낌의 문제였지만, 연결하지 않고 현재 정점에서 몇 개가 이어지는지 갯수만 파악하면 해결되는 문제이다. 쿼리는 총 3가지로 구성되어 있다. 1 u v 로 주어지는 경우 => u와 v가 친구 관계를 맺는다. 즉, 정점을 연결한다고 볼 수 있다. 2 u v 로 주어지는 경우 => u와 v가 친구 관계를 끊는다. 즉, 정점을 끊는다고 볼 수 있다. 3 으로 주어진 경우 => power에 따라 power가 가장 낮은 순으로 친구관계를 맺은 경우 차례로 kill 을 하는 과정에서 가장 마지막에 살아남는 즉, 친구 관계를 맺을 경우..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com 문자열 관련하여 '^' 연산자를 사용하는 문제이다. 아이디어는 다음과 같다. 기존 문자열의 쌍과 기존 문자열의 쌍에 대한 permutated 문자열의 쌍을 각각 '^' 연산을 취해주면 0이 된다. (이때 0을 베이스로 깔고 감) 즉, (2*n - 1) 개의 문자열 중에서 stolen string을 제외한 문자들을 전부 '^' 연산을 한 결과는 0이 됨을 아는것이 중요하다. 풀이 code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #i..

문제 링크 => Problem - C - Codeforces Problem - C - Codeforces codeforces.com Problem tags : greedy, sortings 소팅을 활용한 그리디 알고리즘 문제이다. 문제에서 주어진 n, k, x 에 대해서 알아보자면, n : the initial number of students k : the number of students you can additionally invite x : the maximum allowed level difference 주어진 Stable Groups를 문제에서 주어진 Examples를 통해 알아보려고 한다. input 8 2 3 1 1 5 8 12 13 20 22 이때 8명의 학생이 들어오고 최대 2명을 초대..

문제 링크 => Problem - B - Codeforces Problem - B - Codeforces codeforces.com Problem tags : constructive algorithms, math, number theory 문제의 조건을 보면 다음과 같다. 1 is in this set. If x is in this set, x⋅a and x+b both are in this set. 예를 들어서 a=3, b=5 라고 가정해보자. 이때 1은 기본적으로 set에 포함된다. 그리고 두번째 조건을 통해 1 * 3 = 3 , 1 + 5 = 6 으로 3, 6 값이 set에 포함된다. 3을 기준으로 보면? => 3 * 3 = 9, 3 + 5 = 8 으로 9, 8 값이 set에 포함된다. 6을 기준으..