https://www.acmicpc.net/problem/28354 28354번: 링크 컷 토마토 첫째 줄에 토마토의 개수 $N$, $0$일에 연결되어 있는 토마토 쌍의 수 $M$, $0$일에 익은 토마토의 수 $K$, 연결 상태가 변하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200\,000;$ $0 \leq www.acmicpc.net - 문제 요약 토마토가 꼭지를 안테나처럼 사용해 연결을 형성하고 끊으며 네트워크를 이룬다는 사실은 잘 알려져 있다. 토마토 간의 연결은 날짜가 바뀌는 순간에만 형성되거나 끊어질 수 있으며, 임의의 두 토마토 사이의 연결 상태는 하루에 두 번 이상 바뀌지 않는다. 토마토 네트워크를 전공한 농부 존은 토마토의 연결 상태와 숙성도..

https://www.acmicpc.net/problem/28355 28355번: 무한 수열 세훈이는 생일 기념으로 $ N $개의 정수로 이루어진 수열 $ A $를 선물로 받았다. 하지만 수열의 길이가 너무 짧다고 생각한 세훈이는 다음과 같은 방식으로 무한히 긴 수열을 만들기로 했다. 우선 www.acmicpc.net - 문제 요약 세훈이는 생일 기념으로 N개의 정수로 이루어진 수열 A를 선물로 받았다. (A_i < 2^31 )$ 하지만 수열의 길이가 너무 짧다고 생각한 세훈이는 다음과 같은 방식으로 무한히 긴 수열을 만들기로 했다. 우선 수열 A를 무한히 이어 붙인 뒤, 모든 양의 정수 i에 대해 i번째 수에서 i를 뺀다. 수열의 길이가 길어졌음에 만족한 세훈이는 이렇게 만들어진 수열에서 연속된 몇 개..

https://www.acmicpc.net/problem/28360 28360번: 양동이 게임 절대오차는 실제 정답과 출력값의 차이, 상대오차(오차율)는 절대오차를 실제 정답으로 나눈 값을 의미한다. 즉, 실제 정답을 $a$, 출력값을 $b$라고 하면, 절대오차는 $\vert a - b \vert$, 상대오차는 www.acmicpc.net - 문제 요약 찬우는 천하제일 코딩대회 참가자들과 간단한 게임을 하기로 했다. 게임은 '양동이 게임'으로, 맨 위의 양동이에 물을 100만큼 부어 흘려보냈을 때 최종적으로 가장 많은 물이 담긴 양동이를 선택하면 이기는 게임이다. 양동이를 고르기 전까지는 연결 상태를 알 수 없다. 하지만 찬우는 양동이들이 어떻게 연결되어 있는지 이미 알고 있는 상태였다! 찬우가 게임을 ..

https://www.acmicpc.net/problem/28357 28357번: 사탕 나눠주기 소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 $X$를 정한 뒤 최종 점수가 $X$점을 넘는 학생들에게 점수가 높은 www.acmicpc.net - 문제 요약 소수전공 수업을 마무리한 찬우는 축하의 의미로 학생들에게 사탕을 나누어 주려 한다. 구체적으로, 기준이 되는 음이 아닌 정수 X를 정한 뒤 최종 점수가 X점을 넘는 학생들에게 점수가 높은 만큼 많은 사탕을 줄 것이다. 즉, X+1점을 받은 학생은 1개, X+2점을 받은 학생은 2개, T(T > X)점을 받은 학생은 T - X개의 사탕을 받게 된다. 찬우는 학생들에게 최대한 많..

https://www.acmicpc.net/problem/28358 28358번: 생일 맞추기 첫 번째 테스트 케이스는 아이디에 $0$, $1$, $2$, $3$, $4$가 포함된 경우이다. 태어난 달은 $5$월부터 $9$월 사이, 태어난 일은 $5$일부터 $9$일 사이여야 하므로 생일이 될 수 있는 날짜는 총 $25$개이다. www.acmicpc.net - 문제 요약 많은 사람이 아이디를 지을 때 생일과 관련된 숫자를 넣지만, 찬우의 아이디에서 등장하는 숫자는 태어난 달이나 태어난 일에 등장하는 숫자들과 하나도 겹치지 않는다. 찬우의 아이디에 어떤 숫자가 포함되어 있는지 주어지면, 찬우의 생일이 될 수 있는 날짜의 수를 구해보자. 찬우가 태어난 해는 윤년이다. 즉, 찬우의 생일은 2월 29일이 될 수도..

https://www.acmicpc.net/problem/28359 28359번: 수열의 가치 첫째 줄에 $N$이 주어진다. $(1 \le N \le 1\,000)$ 둘째 줄에 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \le A_i \le N)$ www.acmicpc.net - 문제 요약 어떤 정수 수열 X의 가치는 다음과 같이 정의된다: X에서 감소하지 않는 부분 수열 P와 증가하지 않는 부분 수열 Q를 임의로 선택했을 때, (P의 모든 원소의 합) + (Q의 모든 원소의 합)의 최댓값 길이가 N인 정수 수열 A가 주어진다. A를 원하는 대로 재배열하여 수열의 가치를 최대화하고 싶다. 재배열하여 만들 수 있는 수열의 가치의 최댓값과 이때의 수열을 찾아보자. ..