https://codeforces.com/contest/1883 Dashboard - Codeforces Round 905 (Div. 3) - Codeforces codeforces.com 8월 말에 저는 블루를 찍었고, 그 후에 저는 코드포스를 한 번도 쳐본적이 없었습니다. 티어가 떨어질 수 있다는 불안감도 없진 않았지만 현재 백준 다이아를 찍어보고 싶어서(그래야 연말에 다이아 키링을 받지 않겠어요? ㅎㅎ) 백준에 좀 더 집중하고 있었습니다. 그러다가 최근에 이례적으로 Div.1 ~ Div.3를 동시에 열었다는 소식을 들었습니다. 제가 코드포스를 시작한 후에 처음으로 Div.1 부터 Div.3 까지 열린건데, 그래서 그런지 이번에 Div.2 참가 제한이 블루부터 퍼플까지 였습니다. 딱봐도 레이팅이 떨어..

https://www.acmicpc.net/problem/22343 22343번: 괄호의 값 비교 첫 번째 테스트 케이스: f[A] = f[((()))] = 4이고, f[B] = f[()(())] = 3이므로, f[A] > f[B]이다. 두 번째 테스트 케이스: f[A] = f[(((())))] = 8이고, f[B] = f[()()()()()] = 5이므로, f[A] > f[B] 이다. www.acmicpc.net 문제를 해석해보면 아래와 같습니다. 1. 함수 F가 있는데, F[()] = 1입니다. 2. F[()] = F[] * 2이고, F[] = F[] +F[] 이런식으로 동등한 위치에서의 괄호들의 F 값들은 더하고, 씌워져 있는 만큼 2를 곱해줍니다. 3. 괄호들이 제대로 씌워진 문자열 a,b가 주어..

https://www.acmicpc.net/problem/1578 1578번: 세계 정복 첫째 줄에 국가의 수 N과 K가 주어진다. N은 K보다 크거나 같고, 50보다 작거나 같은 자연수이고, K는 20보다 작거나 같은 자연수이다. 둘째 줄에는 각 나라에 살고 있는 사람의 수가 공백으로 구분 www.acmicpc.net 문제의 조건을 요약하자면 아래와 같습니다. N개의 국가가 있으며 각 나라마다 인구 수가 주어집니다. 그룹이란 K명으로 이루어지며, 그룹 내의 사람들의 국적은 전부 달라야 합니다. 문제에서는 그룹을 최대 몇 개로 나눌 수 있는지를 물어봅니다. 일단 관찰을 해봅시다. 그룹을 G개로 쪼갤 수가 있다면, 맨 마지막 그룹을 버림으로써 G-1개로도 쪼갤 수 있는 걸 알 수 있습니다. 그렇다면, 특정..

https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 문제를 읽어보면 조건들은 아래와 같습니다. 땅과 바다로 구분된 지도가 주어집니다. 상하좌우로 인접한 땅은 하나의 섬으로 봅니다. 목표는 섬을 모두 잇는 겁니다. 두 섬은 바다에 다리를 건설해서 이을 수가 있습니다. 다리는 바다에만 놓을 수 있습니다. 그리고 다리의 길이는 다리가 격자에서 차지하는 수로, 2 이상이 되어야 합니다. 또한, 다리는 중간에 방향이 바뀌면 안됩니다. ..

https://www.acmicpc.net/problem/19585 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net 문제의 조건들을 파악해봅시다. 1. 색상들의 이름들과, 닉네임들이 C, N개씩 주어짐 2. 이후에 Q개의 팀 이름들이 주어질 때, 각 이름들이 이 나온다음에 이 나오는 구조로 이루어져 있는가를 출력 조건만 보면 일단 단순합니다. 문제 길이도 그렇게 길지는 않죠. 다만, 색상의 종류와 닉네임의 개수가 C, N개인데 모든 조합을 파악하기에는 4000 * 4000 개이며, concaten..

https://www.acmicpc.net/problem/14727 14727번: 퍼즐 자르기 히스토그램을 구성하는 직사각형의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 이어 N개의 줄에 걸쳐 각 직사각형의 높이인 정수 Hi(1 ≤ Hi ≤ 1,000,000)가 주어진다. www.acmicpc.net 문제를 읽고 조건들을 파악해보면 아래와 같습니다. 1. 히스토그램의 넓이가 1씩 쪼개어졌을 때의 높이가 주어짐 2. 히스토그램의 내에서 그릴 수 있는 제일 넓은 직사각형의 넓이를 출력 저는 예전에 히스토그램에서 큰 직사각형 찾는 문제들을 푼 경험이 있어서 이 문제의 조건들을 보자마자 Monotone Stack으로 풀 수 있다는 걸 알아차렸습니다. (물론, 분할 정복을 활용하거나, Segment Tr..