본문 바로가기
반응형

컴퓨터 사이언스/BOJ42

[c++] 백준 열혈강호 시리즈 with Network flow (190906) 열혈강호 https://www.acmicpc.net/problem/11375 열혈강호 2 https://www.acmicpc.net/problem/11376 열혈강호 3 https://www.acmicpc.net/problem/11377 열혈강호 4 https://www.acmicpc.net/problem/11378 열혈강호 5 https://www.acmicpc.net/problem/11408 열혈강호 6 https://www.acmicpc.net/problem/11409 Network flow 관련 시리즈 문제이다. 공부하면서 한번에 6문제를 거저먹는 나름의 꿀문제..?이다. 회사 직원이 있고, 일이 있고 한 회사 직원이 하나 혹은 그 이상의 일을 맡고, 하나의 일을 여러명이 맡는 것도 가능한 그런 .. 2019. 10. 8.
[c++] 백준 내리갈굼 시리즈 with 세그먼트 트리 (190906) 내리 갈굼 https://www.acmicpc.net/problem/14267 내리 갈굼 2 https://www.acmicpc.net/problem/14268 내리 갈굼 3 https://www.acmicpc.net/problem/14287 내리 갈굼 4 https://www.acmicpc.net/problem/14288 세그먼트 트리 관련 문제이다. 1, 2는 세그먼트 트리를 곧바로 사용해도 되지만, 야자타임이 발생하는 3, 4번은 약간 응용 같은 느낌이다. 3번은 개별 update, 범위 find를 이용하면 된다. 4번은 개별 tree와 범위 tree 두 개를 동시에 쓰면 된다. 이 때 트리를 별도로 만들어야 한다. 왜냐하면 한 트리에서 야자타임했다가 안했다가 하면 구간합과 개별합이 엉망으로 합쳐지.. 2019. 10. 8.
[c++] 백준 #12920 평범한 배낭 (190903) 보자마자 knapsack 문제가 생각났다. 단순 DP 문제처럼 접근하려 했지만.. But.. 단, 집에 동일한 물건들이 여러개가 있을 수 있기 때문에 한 물건을 두개 이상 챙기는 것도 가능하다. 라는 조건 때문에 평범한 방법으로는 풀 수가 없다.(진짜로 n개씩 다 집어넣어보고 하면 시간초과가 날 것이다.) n이 100만, w는 1만이라서 애초에 dp[n][w]로 배열 선언도 못한다. 그래서, 좋은 아이디어는 1, 2, 4, 8, 16, 32, 64, 128, 256, 1000-511 이런 식으로 해서 묶음을 1000개에서 9개로 바꾸는 것이다. 10000개의 묶음이면 15~16개 정도가 되는 것이고, 많아봤자 물건이 1600개니까. #include using namespac.. 2019. 10. 8.
[c++] 백준 #11447 Colby’s Costly Collectibles (190903) x(1,0) y(1,1) z(-1,1)로 하고 신발끈 공식을 쓰면 된다. 신발끈 공식은 다각형의 넓이를 구하는 방법으로 다각형이 볼록이든 오목이든 가능하다. ** 문제를 풀 때 double을 쓰면 오차가 생기기 때문에 최대한 안쓰는 것이 좋다. #include using namespace std; #define INF 987654321 typedef long long ll; typedef pair ii; typedef tuple iii; #define pb push_back int abs(int a){ if (a>=0) return a; else return -a; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int T;.. 2019. 10. 8.
반응형

티스토리툴바