usaco silver5 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 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. BOJ 14452 - Cow Dance Show (usaco silver, 이분탐색) https://www.acmicpc.net/problem/14452 이분탐색할때 mid값이 문제 조건에 맞는 지 판단하는 isPossible 함수를 짤 때, multiset이나 priority_queue를 이용하고 싶었으나 구현을 못해서 vector로 구현했더니 시간초과가 났던 문제.. Barking dog님의 코드를 참고했습니다. https://github.com/blisstoner/BOJ/blob/master/14452.cpp #include #include #include using namespace std; int n, t; int d[10000]; bool isPossible(int k) { multiset ms; int tot = k, time = 0; for (int i = 0; i < k;.. 2019. 10. 7. 이전 1 2 다음
