알고리즘/백준 & swacademy108 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. BOJ 14170 - Counting Haybales (usaco silver, 차원압축, 세그먼트트리) https://www.acmicpc.net/problem/14170 분류를 차원압축과 세그먼트트리로 하긴 했지만 훨씬 쉽게 풀 수는 있다. 하지만, 차원압축에 익숙해지기 위한 예제로 사용하면 좋을 것 같다. #include #include #include #include using namespace std; const int MAX = 1 = 1; i--) arr[i] = arr[i * 2] + arr[i * 2 + 1]; } int sum(int s, int e, int node, int ns, int ne) { if (e > q; int x[100000], hsize=0; set xSet; unordered_map xHash; //입력 및.. 2019. 10. 3. BOJ 11973 - Angry Cows (usaco silver, 이분탐색) https://www.acmicpc.net/problem/11973 딱 봐도 이분탐색. 구현하는걸 까먹어서 옛날 코드 참고해서 풀었다. 폭발반지름R 대신 폭발구간 R'에 대해 이분탐색하였다. #include #include using namespace std; int n,k,arr[50000]; /* 처음 짠 논리. 밑에서 간략화 했다. bool isPossible(int m) { int i = 0, cnt = 0;; while(cnt= n) break; } return i >= n ? true : false; } */ bool isPossible(int m) { int i = 0, cnt = 0; while(cnt n >> k; for (int i = 0; i > arr[i].. 2019. 10. 1. 이전 1 ··· 17 18 19 20 21 22 23 ··· 27 다음