승형님의 블로그

https://codeforces.com/contest/1766 Dashboard - Educational Codeforces Round 139 (Rated for Div. 2) - Codeforces codeforces.com A. Extremely Round 요약 수를 구성하는 자릿수 중 0이 아닌 수를 단 하나만 가지는 양수의 개수를 구한다. 1. 1 ~ 9, 10 ~ 99, 100 ~ 999 ...로 딱 떨어지는 수를 센 뒤 더해주는 방식을 택한다. 2. 한 자릿수마다 조건에 부합하는 수는 9개이다. #include using namespace std; int t, N; int main(void) { ios::sync_with_stdio(false); cin.tie(0); cin >> t; whi..

https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 요약 주어진 조건으로 처리할 수 없는 좀비가 C개 이하인지 여부를 구한다. 1. 좀비와의 거리와 체력, 기관총의 사거리와 공격력, 지뢰의 개수가 주어진다. 만약 좀비의 체력이 기관총을 쏜 횟수 * 기관총의 공격력보다 높다면, 지뢰를 사용하여야 한다. 2. 기관총을 쏜 횟수 * 기관총의 공격력을 누적합으로 psum이라는 배열로 관리한다. 지뢰와 기관총을 동시에 사용할 수 없으므로, 지..

https://codeforces.com/contest/1771 Dashboard - Codeforces Round #837 (Div. 2) - Codeforces codeforces.com A. Hossam and Combinatorics 요약 n개의 정수로 이루어진 수열이 주어진다. $\left| a_{i} - a_{j}\right|$이 수열에서 최대인 쌍 (i, j)의 갯수를 구한다. 1. $\left| a_{i} - a_{j}\right|$의 최댓값이 0인 경우, 0이 아닌 경우로 나누어 풀 수 있다. 만약 $\left| a_{i} - a_{j}\right|$의 최댓값이 0인 경우, n개의 정수가 모두 같은 수일 때이므로 답은 $n *(n-1)$이 된다. 2. $\left| a_{i} - a_{j..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 요약 바다와 육지로 이루어진 지도에서, 육지에서 육지로 이동하는 최대 최단거리를 구한다. 1. 육지에서 인접한 육지로 이동하는 비용이 1이므로, 모든 가중치가 동일한 무방향 가중치 그래프를 떠올릴 수 있다. 2. 모든 가중치가 동일하고, 최단거리를 구해야 하므로 BFS(너비 우선 탐색) 기법으로 최단거리를 구할 수 있다. 3. 최단거리의 최대 값을 구하기 위해 지도 상의 Brute Force 기법을 ..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 요약 초기에 다른 모든 정점과 단절된 한 정점이 존재한다. 그 정점에서 다른 모든 정점에 간선을 잇는 비용이 주어질 때, 연결그래프를 만들기 위한 최소 비용을 구한다. 1. 이미 연결되어 있는 M개의 간선 정보가 주어진다. 단절된 정점에서 한 정점과 간선을 연결하면 그 정점과 연결된 모든 정점과도 연결되기 때문에, 이미 연결된 두..

https://atcoder.jp/contests/abc280 Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp A. Pawn on a Grid 요약 주어진 격자에서 '#'의 개수를 세어 반환한다. #include using namespace std; int H, W, cnt; int main(void) { ios::sync_with_stdio(false); cin.tie(..