본문 바로가기

알고리즘/백준 & swacademy108

BOJ 11510 - TOPOVI (constructive, greedy) https://www.acmicpc.net/problem/11510 시공간복잡도 파악이 힘들어서 풀이방법 자체가 떠오르지 않았다. 최대 1e9*1e9 정사각형 모양의 한 변의 길이가 n인 그리드위에 룩(rook)을 배치할 것이다. 모든 룩은 1e9 이하의 power를 부여받는다. power가 x인 룩이 (r,c)에 배치된다면, r번 row의 모든 칸의 값에 x를 XOR한 값을 저장한다. c번 column도 마찬가지다. (따라서 칸(r,c)는 두 번 xor되므로 칸(r,c)에 저장된 값은 변하지않는다.) 초기에 최대 1e5개의 룩 k개를 배치한다. (r,c,x) 이후에 최대 1e5번 (r1,c1)에 위치한 룩을 모두 (r2,c2)에 이동시킨다. (r1,c1,r2,c2 ,, 꼭 (r1,c1)에 룩이 있다는 .. 2020. 3. 11.
BOJ 15759 - Talent show (냅색, 이분탐색) https://www.acmicpc.net/problem/15759 어려움 최대 250마리의 소 n마리와 최대 1000의 무게제한W가 주어진다. 각각의 소는 최대 1e6의 무게w와 최대 1e3의 능력t가 주어진다. 소들을 적절히 골라서 무게합이 W이상인 집합 중, 능력합/무게합의 최대값을 x라고 할 때, 1000x의 소수점을 버린 값을 구하라. 고른 소들의 집합을 S라고하면 무게합은 W이상이고 다음을 만족해야 한다. 구해야 할 값은 1000x이므로 이를 y로 치환해서 다시 정리해 보면 다음과 같다. y값 1~250*1000*1000범위에 대해 이분탐색하면 된다. int pos(y) : 능력합/무게합이 y가 가능한지? dp[k] : 무게 합이 k일 때 1000T - yW의 최대값 dp[W] : 무게합이 W.. 2020. 3. 1.
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.

티스토리툴바