USACO7 BOJ 12003 - Diamond Collector (전처리) https://www.acmicpc.net/problem/12003 유사코엔 전처리문제가 많이나온다 보석의 크기가 최대 5e4개 주어진다. 이 보석들을 두 개의 케이스에 나눠 담고 싶은데, 같은 케이스에 있는 보석의 크기 차이가 최대 K가 되도록 나누고 싶다. 최대한 보석을 전시한다면 몇개를 전시할 수 있을까? p[i] : 보석들중 크기가 a[i]~a[i]+k인 것들의 개수 pmx[i] = i~n-1번 보석 중 p[i]값의 최대 i번 보석을을 1번 케이스에 넣을 때 최대 전시 보석 수 = p[i] + pmx[i+p[i]] #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); u.. 2020. 2. 7. BOJ 12012 - Closing the farm (유니온파인드) https://www.acmicpc.net/problem/12012 거꾸로 생각해서 쉬워지는 문제 최대 2e5개의 정점과 간선으로 이뤄진 양방향 그래프가 주어진다. 정점의 개수를 n이라고 할때 쿼리가 n개 들어온다. 각 쿼리에선 정점이 하나 주어지는데(u), 현재 전체 컴포넌트의 수가 1이라면 YES를, 1이상이라면 NO를 출력한 후, 해당 정점과 정점에 연결된 간선을 모두 지운다. 문제 설명대로 완성된 그래프에 간선을 지워가면서 컴포넌트의 수를 log시간 이하로 구하는 것은 매우 어렵다. (불가능한 것 같다) 쿼리를 기록해두고 거꾸로 접근하면, 아무것도 없는 그래프에 정점과 연결된 컴포넌트를 이어주며 컴포넌트의 개수를 유지하는 문제로 바뀐다. 정점u를 추가할 때 이미 그래프에 추가된 정점들에 대해서만 .. 2020. 2. 7. BOJ 15590 - Rental Service (usaco silver, 그리디, 구간합배열, 이분탐색) https://www.acmicpc.net/problem/15590 그리디 + 이분탐색 + 구간합배열로 풀었다. 생각한 순서는 1. 모든 소 N마리에 대해 i번쨰 소를 우유를 팔거나, 빌려주거나 하는 완탐 -> (O(2^1000000) 시간초과 2. 소의 우유 산출량을 내림차순 정렬한 후, 0~i번째 소는 우유를 팔기로 한다면, i+1~n-1번쨰 소는 반드시 빌려줘야 한다. 빌려주는 경우는 간단하게 처음부터 더해주면 되기 떄문에 그에 맞는 구간합배열을 저장해 뒀다면 상수시간에 도출할 수 있다. 문제는 0~i번째 소의 우유를 팔때의 수익을 반환하는 함수의 논리이다. 그냥 앞에서부터 긁어주면 O(i)로 할 수 있는데, 이렇게 되면 시간 초과가 난다. (p,q)를 q에 대해서 내림차순으로 정렬한다면, 다음과 .. 2019. 10. 11. BOJ 15462 - The Bovine Shuffle(usaco silver, dfs) https://www.acmicpc.net/problem/15462 int arr[] : 각 위치에 소가 몇마리 있는지 int odr[] : 다음 위치 가리키는 배열 int mcnt[] : 각 위치마다 배치됐던 소의 최소값. 초기상황 : 배열에 소가 1마리씩 들어있음 위치에 따라 다음 이동 위치가 주어지기 때문에 dfs, bfs를 생각했으나 현재 상태를 어떻게 표현해야할지 감이 안와서 이런 생각을 해봤다. "무한히 시뮬레이션 하는데 제한시간이 주어졌다는 것은 반복되는 상태가 생긴다는 뜻이고, bfs dfs로 풀 수 있다는 건 시뮬 돌리다보면 시간 안에 답이 나온다는 뜻이니까 시간에 맞게 최대한 시뮬 돌려보면 나오지않을까?" shuffle 1회에 O(1e5), 전체 O(le8)안에 끝내야 하므로 시뮬을 1.. 2019. 10. 9. 이전 1 2 다음
