usaco gold5 BOJ 15758 - Milking order (이분탐색, 위상정렬) https://www.acmicpc.net/problem/15758 최대 5만개의 법칙 M개가 주어진다. 법칙마다 순서가 주어진다. 예를들어 1 4 3이면 최종 결과에 1 4 3 이 순서대로 나타나야 한다. 앞에서부터 최대한 많은 법칙을 사용해서 유효한 n의 permutation을 만들고자 할 때, n의 permutation을 구하라. 앞에서부터 법칙 1개 ~ m개를 만족할 때에 대해 가능한지 이분탐색한다. bool pos(int k) 함수에서 앞에서부터 k개의 법칙을 이용해서 위상정렬 가능한지 반환하면 된다. 단, 가능한 수열 중 사전 순으로 가장 앞선 수열을 출력해야하므로 위상정렬시 pq를 쓰면 된다. int n, m, ind[MAX]; vector odr[50004]; vector topo; vec.. 2020. 3. 1. BOJ 15745 - Snow boots (오프라인 쿼리, 유니온 파인드) https://www.acmicpc.net/problem/15745 최대 1e5개의 음이 아닌 정수 n개가 주어진다. 첫번째와 마지막은 0임이 보장된다. 쿼리 s d가 최대 1e5개 주어진다. 배열에서 s를 초과하는 연속하는 부분수열의 최대 길이 < d인 경우 1을, 그 외엔 0을 출력한다. s에 대해 내림차순으로 query를 정렬한다. 각 쿼리마다 배열에서 서로 인접하면서 s를 초과하는 값을 갖는 인덱스끼리 merge해준다. (한 번 처리한 값을 중복해서 처리하지 않도록 한다) 그러면 각 쿼리마다 집합들 중 최대 크기가 s를 초과하는 연속하는 부분 수열의 길이가 된다. 쿼리마다 O(lgN)에 최대값을 찾고 모든 쿼리에 걸쳐 인덱스에 대해 한번씩만 연산하므로 O(QlgN+N)쯤 될 것 같다. int n,.. 2020. 3. 1. BOJ 15475 - A pie for a pie (이분그래프, 이분탐색) https://www.acmicpc.net/problem/15457 유사코 골드. bessie와 elsie가 서로 선물을 교환한다. 같은 선물에 대해 각자 생각하는 가치가 다를 수 있다. 최대 1e5개의 선물을 둘이 같은 개수만큼 가지고 있다. 서로 선물을 교환하려 한다. 예를들어, bessie가 볼때 3의 가치를 지닌 선물을 bessie가 받은 경우 3이상 3+d이하(bessie기준)선물을 elsie에게 보답으로 준다. elsie도 마찬가지다. 이런 방법으로 계속 선물을 교환할 때, 본인이 생각했을 때 가치가 0인 선물을 받으면 성공적으로 선물 교환이 이뤄진 것으로 본다. bessie부터 선물을 주기로 한다. bessie의 i번째 선물을 처음으로 elsie에게 줬을 때 가장 적은 횟수로 성공적인 선물교.. 2020. 2. 18. BOJ 12013 - 248게임 (dp) https://www.acmicpc.net/problem/12013 dp[i][j] : 구간[i,j]~~ 40이하의 자연수가 최대 248개 주어진다. 인접한 두 수가 같다면 1을 더한 값으로 합칠 수 있다. (7,7,1->8,1) 더이상 합칠 수 없을 때까지 합친 후에 남아있는 수 중 가장 큰 수의 최대값을 구해라. dp[i][j] : i~j를 합할때 남아있는 수 중 가장 큰 수. dp[i][i]=a[i] dp[i][j] =if(dp[i][k]==dp[k+1][j]) max ( dp[i][k]+1; ) i~j간격 1부터 차례로 갱신해야 하는 것에 주의. for문의 가장 바깥에 해당하는 것이 간격임. (코드의 sz) 모든 d중 최대값이 정답 #include #include #include #include .. 2020. 2. 7. 이전 1 2 다음