정보과학 (Informatic)/PS (4) 썸네일형 리스트형 [BOJ] 16602 Brexit Negotiations (NWERC 2018) 문제 설명 및 요약 $N$ 개의 회의가 있으며 각 회의별로 진행 시간과 선행되어야 하는 회의의 번호가 주어진다. 후행 회의는 선행 회의가 아직 진행하고 있어도 이미 시작하기만 했다면 시작할 수 있다. 회의들은 동시에 진행될 수 있지만 매 시간 1개의 회의밖에 시작하지 못한다. 모든 회의가 끝날 때까지 걸리는 시간의 최소값을 구하여라. 풀이 전형적인 그리디 문제의 일종이다. 이 문제의 핵심은 한 회의가 진행되는 동안 다른 회의들도 진행될 수 있다는 것이다. 즉 회의 시간이 긴 회의를 앞쪽에 배치한다면 그 회의를 시작한 후에 두 번째 회의를 시작할 때 두 번째 회의가 끝난 후에도 첫 번째 회의는 진행 중일 가능성이 높기 때문에 총 회의 시간은 크게 변하지 않아 이득이라는 것이다. 이 아이디어를 이용해보자. .. [BOJ] 10075 친구 (IOI 2014) // [KOISTUDY] 1457~1459, 1461~1463 친구 1~6 Taipei에서 열린 IOI 2014에 출제되었던 문제로 어려워보이는 난이도와는 다르게 모범코드는 매우 짧으며 명확한 문제이다. 모든 정보가 주어진 상태에서 역행하면서 "같은 답을 얻을 수 있지만 정점의 수는 적은 그래프" 로 주어진 그래프를 변환하여 풀면 쉽게 해결된다. i번째 프로토콜로 WeAreYourFriends 가 입력됬다고 하자. WeAreYourFriends 프로토콜을 처리하면서 주목할 점은 host 와 사람 i를 동시에 표본에 포함시킬 수는 없지만 host 또는 사람 i가 표본에 포함되었을 때에는 상대방과 host 의 친구들은 모두 표본에 포함시킬 수 없다는 점이다. 이 사실을 바탕으로 그래프에서 사람 i 가 존재하지 않는 동치 그래프로 바꾼다면 host 의 신뢰도를 $trust[host].. [BOJ] 5257 timeismoney 문제가 영어라 혼동되는 분들을 위해 핵심을 적어보자면 다음과 같다. $N$ 개의 정점이 존재한다. $N-1$ 개의 무향 간선으로 이 정점을을 모두 잇고 싶다. $M$ 개의 간선이 들어오며 각 간선마다 건설할 때 필요한 시간과 비용이 존재하는데 $N-1$ 개 간선들을 건설할 때 걸리는 시간의 합과 소모되는 비용의 합의 곱이 최소가 되도록 만들고자 한다. 총 시간의 합과 총 비용의 곱의 최소값은 얼마인가? (단 두 정점을 잇는 간선은 한 개만 들어오며 건설해야하는 간선의 번호까지 출력해야 한다 Kruskal algorithm을 이용하면 시간의 합의 최소와 비용의 합의 최소는 쉽게 구할 수 있다. 그런데 이 둘의 곱의 최소는 어떻게 구할 수 있을까? 우선 간단한 아이디어로 구할 수 있는 "최소"의 틀을 확장시.. [KOISTUDY] 수열과 쿼리 [2124 / 084C] http://koistudy.net/?mid=prob_page&NO=2124 KOISTUDY Informatica Online Judge Time Limit(Test case) : 5000(ms)Number of users who solved : 9 Total Tried : 64 The Champion of this Problem (C++) : gs16044 - ms / 1134byte My Best Submission (C++) : N/A [koistudy.net (34th 김현수)] Background 현수는 수열과 쿼리 문제 시리즈의 추 koistudy.net 기본적인 틀은 간단하다. $i$~$j$ 범위 안의 $k$ 의 개수를 구하는 것은 우선 merge sort tree 를 형성해주고 1 2 3 .. 이전 1 다음