문제만 보면 쉬워보이는 문제다. 실제로 어렵지는 않은 문제지만, 무작정 코드를 작성하기 보다는 어떤 자료구조를 사용해서 설계할 것인지 미리 생각해보고 프로그래밍하는 것을 추천한다. 나도 무작정 코드를 작성하기 시작했다가 set과 map 중 어떤 것을 사용해야할지 계속 고민하면서 수정했다. 문제를 간단하게 요약하면 플레이어의 중복은 허용하지 않으며 지정된 플레이어 수를 만족하면 게임을 시행할 수 있다. 그러면 우리가 해야할 것은 -중복 체크 -플레이하는 플레이어 수 체크 이 두가지이다. 플레이어 한명씩 입력받으면서 해당 사람이 중복된 사람인지 체크했다. 만약 중복이 아니라면 다음에 중복을 체크하기 위해 set에 insert하고, 플레이가능한 사람의 수인 cnt를 1증가시켰다. 이때 cnt+1(임스)가 플레..

문제에 숨어있는 힌트들을 잘 파악하는 것이 중요한 문제였다. 우선 x는 증가하는 방향으로만 이동이 가능하다. y는 방향에 제한이 없는데 문제를 잘 읽어보면 힌트가 있다. "이 산책로는 단순 경로이며 수평 구간과 수직 구간으로만 구성되어 있어 모든 코너에서 90도 각도로 왼쪽 또는 오른쪽으로 회전만 할 수 있다." 위의 문장을 보면 코너에서 180도 회전이 불가능하다. 즉, 왔던 길을 되돌아갈 수 없고, 한 수직선상에서는 한 방향으로만 움직일 수 있다. 이 의미를 알 수 있으면 구현하기 굉장히 쉬워진다. n, x, y의 최댓값이 100,000 이므로 O(nlogn) 혹은 O(n) 의 알고리즘으로 해결해야한다. 이 또한 문제에서 "그는 산책로를 직접 걷지 않고 카페의 좌표들만으로 이 작업을 수행하고 싶어 한..

이 문제는 강한 연결 요소, 즉 scc에 대해 공부해 볼 수 있는 문제다. scc는 방향 그래프에서 서로 이동할 수 있는 정점들의 모음(?)이다. 그래프에서 사이클을 떠올리면 이해하기 쉽다. scc는 Kosaraju's Algorithm을 사용하면 쉽게 구할 수 있다. 우선 그래프의 모든 정점에 대해 dfs를 한 번 돌린다. 그러면 dfs를 돌면서 방문한 정점들의 순서를 알 수 있다. (단, 이 때 방문 시점은 해당 정점을 빠져나간 시점이다.) 주어진 그래프의 간선의 방향을 모두 반대로 뒤집은 그래프를 대상으로 위에서 구한 순서의 역순으로 dfs를 돌리면 한 번의 dfs에서 방문한 정점들이 scc이다. 이 설명을 듣고 그래프를 그려본 다음 흐름을 따라가보면 왜 dfs 방문 순서의 역순으로 뒤집은 그래프를..

문제를 보자마자 막연히 드는 풀이 방법은 A에서의 관계와 B에서의 관계가 다른 쌍을 찾는 방법이다. 즉 A에서는 i보다 j가 뒤에 있지만, B에서는 앞에있거나 혹은 그 반대의 관계이면 서로 교차한다. 그럼 모든 A에 대해 B를 검사하면O(n^2)의 시간 복잡도로 풀 수 있지만, n이 최대 50만이므로 시간 초과가 발생한다. 일단 교차하는지 확인해야 하기 때문에 모든 A 혹은 모든 B를 검사하긴 해야할 것 같다. 그럼 대충 O(nlogn)인 코드를 작성하도록 해보자. 모든 A에 대해 검사한다고 가정하자. A[0]부터 먼저 처리하면 A[0]에 해당하는 B의 뒤에 있는 기계 중 이미 처리한 기계의 개수가 A[0]와 교차하는 기계의 개수다. 예제에서 132를 먼저 처리해보도록 하자. B에서 132 뒤에 있는 기..

처음에는 오름차순 우선순위 큐와 내림차순 우선순위 큐를 만들어서 시도했다. 이렇게 하면 게시판에 있던 반례하나를 해결할 수 없게 된다. 게시판을 돌아다니다가 multiset이라는 사기적인 자료구조를 알게 되었다. 힙구조라서 원소를 삽일할 때마다 자동 정렬되는데 원소 삽입이 O(logn)이고, 최댓값, 최솟값 찾기도 O(logn)이다. 마치 이 문제를 위해 존재하는 듯 했다. 정답 #include #include using namespace std; int t, k; int main(){ cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false); //input cin >> t; while(t--){ cin >> k; //calculate multis..

최대 힙과 유사한 문제였다. C++에서는 priority_queue의 인자로 greater와 less를 이용해 최소 힙과 최대 힙을 만들 수 있다. greater와 less가 어떻게 구현되어있는가를 보면 어떤 것을 선택해야 최소힙이 될지를 쉽게 알 수 있다. greater는 위와 같이 구현되어 있다. x가 y보다 클 때 참을 반환하는데 쉽게 이해하자면 참일 때 x와 y를 스왑한다고 생각하면 된다. 즉, y가 더 작을 때 스왑하는 것이므로 더 작은 것이 앞으로 오게되는 내림차순형태와 같다. 이를 이진트리에 적용하면 더 작은 것이 루트노드에 가까워지는 것이다. 따라서 가장 작은 원소가 루트노드에 있게 된다. 정답 #include #include using namespace std; int n, x; prio..