본문 바로가기

728x90

전체 글

(32)
백준 18847. Stray Cat (JOISC 2019/2020 Day 3 3번) 문제 설명(링크): https://www.acmicpc.net/problem/18847 18847번: Stray Cat The sample grader is the file grader.cpp. In order to test your program, put grader.cpp, Anthony.cpp, Catherine.cpp, Anthony.h, Catherine.h in the same directory, and run the following command to compile your programs. g++ -std=gnu++14 -O2 -o grader grader www.acmicpc.net 문제 요약 투스텝 문제인데, 첫 번째 실행에는 그래프가 주어져서 그래프 간선에 $A$ 미만의 음이아닌 정..
백준 15261 Donut Drone (CERC 2017 D) 문제 설명(링크): https://www.acmicpc.net/problem/15261 15261번: Donut Drone The first line contains two integers r and c (3 ≤ r, c ≤ 2 000) — the number of rows and the number of columns of the toroidal grid. The i-th of the following r lines contains a sequence of c integers ei,1, ei,2, . . . , ei,c (1 ≤ ei,j ≤ 109) — www.acmicpc.net 문제 요약 도넛처럼 생긴 격자판에서 각각의 높이가 있는데, 한 칸에서 시작할 때 다음으로 갈 칸은 왼쪽 위, 왼쪽, 왼쪽 ..
백준 8987 수족관 3 (KOI 2013 4번) 문제 설명(링크) https://www.acmicpc.net/problem/8987 8987번: 수족관 3 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(4 ≤ N ≤ 300,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 풀이 풀이가 다양한 것 같은데, 내가 푼 풀이 기준으로 설명하겠다. 우선 수족관의 모양이 히스토그램과 유사하므로, 카르테시안 트리로 모델링할 수 있다. 수족관을 카르테시안 트리로 모델링하면 특정 정점을 선택하면 그 정점과 그 정점의 모든 조상 정점에 해당하는 영역의 물이 빠진다. 또한 한번 물이 빠진 영역은 당연하게도 물을 다시 뺄 수 없다. 이런 특성들..

728x90