codeforce (12) 썸네일형 리스트형 C. Rooks Defenders - Codeforces Round #791 (Div. 2) 공격을 받게 되는지 아닌지 체크를 할 때, 일일히 row와 column들을 확인하게 되면, 시간초과가 나게 된다. 그래서 segment tree를 이용해서 row 또는 column에 있는 룩의 개수를 확인해주면 된다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; import java.util.stream.Collectors; public class Main { public stat.. C. Binary String - Educational Codeforces Round 128 (Rated for Div. 2) Binary Search를 사용하는 문제입니다. 삭제된 1의 개수와 남아있는 0의 개수 중 큰 값의 최소값을 찾아야됩니다. 삭제하는 1의 개수를 binary search로 찾아야됩니다. 1을 삭제하면, 뒤에 있는 0들도 같이 지우는 것이 이득입니다. 그래서 1을 하나 지울 때 지워지는 0의 개수들을 저장해둡니다. 앞과 뒤 양방향에서 지울 수 있으므로 배열 2개를 이용해서 지워지는 0의 개수들을 저장해둡니다. 이제 binary search로 삭제하는 1의 개수를 찾습니다. import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; import java.util.stream.Collec.. Codeforces Round #641 (Div.2) A. Orac and Factors f(n)은 n을 나누는 가장 작은 소수를 출력한다. 에라스토테네스의 체를 사용하여, 10^6 까지의 n에 대하여 f(n)을 구한다. 코드에서는 minDiv배열에 해당값을 저장하였다. n = f(n) + n 을 k번 반복한다. test case의 수가 100개 k가 10^9 개 이므로 k번 반복해서는 time out이 발생한다. 두번째 계산부터 f(n)은 무조건 2인데, 이는 f(n) + n의 값이 무조건 짝수이기 때문이다. f(n)이 홀수 일경우 n도 홀수이고, f(n)이 짝수인경우는 n또한 짝수이다. 이를 통해 답을 계산하면, ans = f(n) + n + (k-1) * 2 가 된다. #include using namespace std; int minDiv[1000010]; int main(){ int.. Codeforces Round #635 (Div. 2) C. Linova and Kingdom 문제 왕궁에는 n개의 도시가 있고, n-1개의 양방향 도로를 도시에 연결한다. 도시는 1번부터 n번까지 숫자가 붙여져있다. 1번 도시가 수도이며, 왕국은 트리 구조이다. 여왕은 정확히 k의 도시에 산업을 발전시키며 다른 도시들은 관광산업을 발전시킨다. 회의는 1년에 한번 수도에서 진행되는데, 각 산업 도시에서는 대표들을 수도로 보낸다. 대표들은 최단 경로를 따라서 수도에 이동한다. 관광도시를 여행하는 것은 즐겁고, 각 대표의 행복도는 수도에 이동하는 동안 방문한 관광도시의 개수이다. 여왕은 k의 산업도시를 잘 배치해 대표들의 행복도의 합을 최대로 하고 싶다. 풀이 산업도시가 수도와 얼마나 떨어져 있는지, 즉 depth 값이 각 산업도시의 행복도이다. DFS로 모든 노드를 방문하여, Depth의 내림차순으.. Codeforces #618 (Div. 2) B. Assigning to Classes 학생들을 두개의 class로 나누고, 두 class의 median 값의 차를 최대한 줄여야 한다. 배열 a가 정렬이 되어있다고 하면, 두 class의 중앙값은 a[n-1]과 a[n]이 되어야 그 차이가 최소가 된다. 만약 한 class의 중앙값이 a[n-2]으로 설정이 되었다면, 다른 클래스의 중앙 값은 아무리 작아도 a[n] 이 된다. #include #include using namespace std; int main(){ int t, n; cin >> t ; while (t-- ){ cin >> n; int a[200010]; for (int i = 0; i > a[i]; } sort(a, a+ 2*n); cout Codeforces #618 (Div. 2) A. Non-zero a[1]부터 a[n]까지 n개의 수를 입력받는다. ai = ai + 1 을 수행할 수 있고, a[1] + a[2]+ ... + a[n] 이 0 이 아니고 a[1]*a[2]*...a[n] 이 0이 아니게 되도록하는 최소 +1의 회수를 출력하는 문제이다. a[i]가 0이 되면 안되므로, a[i]가 0이면 +1을 해준다. 그리고 총합이 0이된다면, 양수인 a[i]에 +1을 해주면 문제의 조건에 만족하는 수열을 만들 수 있다. #include using namespace std; int main(){ int t, n; cin >> t ; while (t-- ){ cin >> n; int a[110]; int addCnt = 0; int sum = 0; for (int i = 0; i < n; i ++){ cin.. Codeforces Round #616 (Div. 2) B. Array Sharpening 입력받는 n개의 수들이 k번째까지 증가하고, k부터 n번째까지 감소하는 수열이라면 해당 배열을 sharpened 라고 한다. 여기서 각수들을 1만큼 무한정 뺄 수 있다. 나는 이 수열을 뺄 수 있을 만큼 다 빼보았을 때 어떤 형태가 되는지 생각해보았다. 간단하게 n이 4와 5일 때를 생각해보았다. 1)n = 4 인경우 0 1 2 0 또는 0 2 1 0 이 된다. 2)n = 5 인경우 0 1 2 1 0 의 경우가 최소가 된다. 위 경우로 미루어보아 홀수의 경우 중앙이 최대값이고, 짝수의 경우는 정확한 중앙이 없으므로 최대값의 위치가 2가지로 나타난다. 이를 정리해 코드로 작성하면 된다. #include #include using namespace std; int main(){ int t,n; cin >> .. Codeforces Round #616 (Div. 2) A. Even But Not Even 각 자리수의 합이 짝수인 수를 ebne(even but not even) 이라고 합니다. 주어진 인풋에서 특정 자리수를 제거하여 ebne을 만들 수 있으면, 그렇게 만든 수를 출력하고, 없으면 -1을 출력하는 문제입니다. 홀수 2개만 있으면 ebne을 만들 수 있으므로, input string에 대해서 0번째 위치부터 linear search를 하며 홀수 2개를 찾으면 그 2개를 붙여서 return 하고, 못찾으면 -1을 return하는 코드를 작성하면 됩니다. #include #include using namespace std; int main(){ int t, n; string s; cin >> t; for (int i = 0; i > n; cin >> s; string.. 이전 1 2 다음