https://www.acmicpc.net/problem/25639시간 제한메모리 제한1초512MB문제길이가 N인 수열 a_1, a_2, ..., a_N이 주어졌을 때, 다음과 같은 쿼리를 수행하는 프로그램을 작성해보자.1 k x : a_k를 x로 바꾼다.2 l r : 구간 [l,r]의 최대 상승 값을 출력한다. 구간 [l,r]의 최대 상승 값은 다음과 같이 정의한다.max(a_j - a_i) (l ≤ i ≤ j ≤ r) 입력첫째 줄에 수열의 길이 N(1 ≤ N ≤ 100,000)이 주어진다.두 번째 줄에 수열의 원소 a_1, a_2,..., a_N이 주어진다. 수열의 i번째 원소는 정수 a_i(-10^9 ≤ a_i ≤ 10^9)이다.세 번째 줄에 쿼리의 개수 Q(1 ≤ Q ≤ 100,000)가 주어진다..

https://www.acmicpc.net/problem/15730 시간 제한메모리 제한2초128 MB문제수영장 사업을 시작하려는 수형이는 산의 자연을 훼손하지 않고 지형을 그대로 이용한 수영장을 만들기로 한다. 그래서 물이 고일 수 있는 부분에만 물을 채워넣는 방법을 사용하기로 한다. 이때 수형이는 여기서 얼마만큼의 물을 채울 수 있는지 궁금해 하는데, 땅의 정보가 주어졌을 때 얼마만큼의 물을 채울 수 있는지 출력하는 프로그램을 작성하시오. 입력첫째 줄에 N, M(1 ≤ N, M ≤ 100)가 주어진다. 다음 N 줄동안 매 줄마다 M개의 H(0 ≤ H ≤ 10,000)가 주어진다. 여기서 i 번째 줄의 j 번째 정수를 H[i][j] 라고 할 때, H[i][j]는 해당하는 땅의 높이이다. 출력최대한 물을..

시간 제한메모리 제한1초1024MB문제코코는 초콜릿 공장을 운영하고 있다. 이 공장의 기계는 초콜릿을 3 * N 크기(가로 N, 세로 3)의 직사각형 덩어리로 생산한다. 코코는 이 덩어리를 floor(3N/2)개의 1 * 2 또는 2 * 1 크기의 초콜릿으로 나누어 판매하려고 한다. 어째서인지 N이 항상 홀수라서, 코코는 1 * 1 조각을 하나 골라서 잘라 먹고 남은 부분을 나누어 팔기로 했다. N의 값과 코코가 먹은 조각의 위치(R행 C열)가 주어졌을 때, 남은 초콜릿 덩어리를 나누는 방법의 수를 계산해보자. 입력첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스마다 N, R, C의 값이 한 줄에 주어진다.1 ≤ T ≤ 1e51 ≤ N ≤ 1e5, N은 홀수1≤ R ≤ 3, 1 ≤ C ≤..

https://www.acmicpc.net/problem/32721 시간 제한메모리 제한1초1024MB문제건덕이가 설립한 오리 왕국은 1부터 N까지 N개의 도시로 이루어져 있다. 각 도시는 다른 도시로 향하는 일방통행 도로를 단 한 개만 가지고 있다. 왕국을 다스리던 건덕이는 어떤 도시에서 도로를 이용해 도달할 수 없는 도시가 있음을 알아챘다. 건덕이는 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 도로를 최소한으로 수정하기로 했다. 건덕이는 도로를 아래와 같은 방법으로 수정한다. 도시 A에서 출발하는 도로의 목적지를 수정한다. (1 ≤ A ≤ N ) 건덕이를 위해 어떤 도시에서 출발하더라도 모든 도시를 방문할 수 있도록 만드는 도로의 최소 수정 횟수를 구해주자! 입력첫째 줄에 도시의 개수 N..

1. SCC문제1) SCC 구성하기백준 2150번 Strongly Connected Component백준 11097번 도시 계획 : 최소 간선으로 scc를 만족하는 그래프 만들기백준 25488번 토큰 : [★★★] scc별 빨간 카드, 파란 카드에 적힌 숫자의 수 비교하기백준 1506번 경찰서 : [★★] scc마다 최소 비용만 찾아서 다 더하기 2) a에서 b까지 가장 많은 정점을 방문하는 경로백준 1471번 사탕 돌리기 : [★★★] 모든 정점의 진출차수가 1인 그래프백준 19649번 미담 전하기 : 직접 전파자를 포함하지 않아야 하는 조건 처리가 까다로움백준 2152번 여행 계획 세우기 : [★★★] 같은 컴포넌트의 요소들은 크기만 알면 방문한 셈 칠 수 있음백준 4013번 ATM : [★★★★★]..

시간 제한메모리 제한10초 / 3128MB / 128MB문제https://www.acmicpc.net/problem/2782로맨틱왕: 최대 16개의 선물나무를 선택하거나, 선택하지 않을 수 있으며 선물나무를 선택할 때마다 왕이 1칸을 이동하는데 소모되는 시간이 1씩 증가한다. 왕은 처음에 1칸 당 1시간의 속도로 이동할 수 있다. 왕이 왕비가 있는 곳까지 제한 시간 내에 가져갈 수 있는 최대 선물의 수를 구하는 문제. 선물나무의 위치에 도착했다고 반드시 선물을 가져가는 건 아니고 선물나무마다 선물을 1개 까지 가져갈 수 있다. https://www.acmicpc.net/problem/8138Tourist Attractions: 1~n까지의 지점을 두고 연결 그래프의 형태로 그려진 관광지에서 1에서 출발해..

시간 제한메모리 제한1초256MB문제고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승부가 나서 N명의 선수들의 순위표가 만들어졌다.순위표를 본 현수는 절규하였다. ‘내가 공동 꼴지라고? 꼴지라니... 아니, 내가 꼴지라니! 이게 무슨 소리야! 아핡핡핡’ 이윽고 현수는 자기합리화를 하기 시작했다. ‘내가 한용이를 이겼고, 한용이는 세찬이를 이겼고, 세찬이는 찬우를 이겼고, 찬우는 태양이를 이겼고... 그러니 내가 나머지 전부를 이겼네!’ 현수와 마찬가지로 공동 꼴지인 태양이는 현수와 함께 자기합리화를 해보려고 하지만, 태양이는 나머지 4명을 모두 이기는 방법..

https://www.acmicpc.net/problem/6498시간 제한메모리 제한1초128MB문제엘리어스 감마 코드는 양의 정수로 이루어진 수열을 인코딩 하는데 사용하는 코드이다. 이 문제에서는 0도 인코딩할 수 있게 변형한 코드를 사용한다. 정수 n을 인코딩하는 과정은 다음과 같다.1. n의 비트의 개수를 k라고 한다. 2. 0을 k-1개 쓰고, 그 뒤에 1을 쓴다. 3. 그 다음 n을 이진수로 쓴다.0부터 8까지 숫자를 인코딩한 결과는 아래와 같다.숫자이진수비트의 수Prefix코드0011101111112102010110311201011141003001001100510130010011016110300100111071113001001111810004000100011000 정수 수열을 인코딩하려면, 수..