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 정수 수열을 인코딩하려면, 수..

https://www.acmicpc.net/problem/18858시간 제한메모리 제한1초1024MB문제훈련소로 가는 날 욱제는 문득 떠올렸다. 훈련소가 논산에 있는 이유는 무엇일까? 왜 why? 그것은 바로…            논산(non-산)은 산이 아니기 때문이다. 길이가 3인 수열 a1, a2, a3가 산임은 a1  a3임을 의미한다. 어떤 수열이 논산임은 수열의 인접한 세 항이 산인 경우가 없음을 의미한다. 다시 말해, 길이 N의 수열 a에 대해 2 ≤ i  ai+1인 경우가 없다. 논산인 수열이 몇 개가 있는지 알아보자.입력첫째 줄에 N과 M이 주어진다.1 ≤ N ≤ 1,0001 ≤ M ≤ 100 출력1 이상 M 이하의 정수로 이루어진 길이 N의 수열 중 논산인 것의 개수를 998,244,3..

https://www.acmicpc.net/problem/11781 시간 제한메모리 제한1초256MB문제엔지니어의 행복도는 퇴근 후 집에 도착하는 시각이 늦을수록 낮아진다는 것이 증명되었다.조이의 대표 레드는 엔지니어의 행복도를 최대한 높여야 할 의무가 있기 때문에, 신중하게 퇴근 시간을 조정하기로 하였다.하지만 퇴근 시간을 조정하려면 먼저 엔지니어들이 집에 도착하는 시간을 알아야만 했다.이 문제를 미카에게 맡기려고 했지만, 6시가 넘어 미카는 이미 퇴근해버렸기 때문에 레드는 고민에 빠지고 말았다.레드를 도와 레드와 조이 엔지니어 모두의 행복도를 높여보도록 하자!회사가 있는 서울은 N개의 지점으로 되어있다.각 지점은 1번부터 N번의 번호를 가지고 있고, 회사는 1번 지점에 있다.M개의 도로들은 서로 다른..

https://www.acmicpc.net/problem/31537시간 제한메모리 제한1초1024MB문제누구나 그렇듯 동우는 출근하기 싫다. 그래도 출근해야 한다. 동우가 다니는 회사는 신기한 회사이다. 총 N명의 직원이 있는데, 이 중 최대 1명이 출근하지 않아도 업무를 정상적으로 진행할 수 있다. 하지만  1명보다 많이 출근하지 않으면 업무를 정상적으로 진행할 수 없다.동우는 회사의 업무가 정상적으로 진행되는 것이 신기해 현재 시각으로부터 최근 M시간 동안 N명의 직원 각각이 총 몇 시간씩 출근했는지 살펴보았다.직원들은 모두 정각에만 출근해 정각에만 퇴근하며, 한 사람이 여러 번 출근 혹은 퇴근할 수 있다. 최근 M시간 동안 업무를 계속 정상적으로 진행할 수 있도록 하는, N명의 직원이 출근한 조합의..