전체 글 썸네일형 리스트형 BOJ)2419 사수아탕 문제:icpc.me/2419 사탕이 담긴 사탕바구니가 x축위에 있고 1초마다 사탕 바구니의 사탕이 1개씩 사라질 때 수아가 먹을 수 있는 최대의 사탕 수를 구하는 문제이다. 문제가 다이나믹 프로그래밍임은 쉽게 알 수 있었지만 먹을 수 있는 최대의 사탕수에 포커스를 맞추니 어려워진 문제였다. 이를 dp[l][r][state]로 해결해야하는데 l에서 r까지 사탕을 커버하고 state(왼,오)에 서있을 때 먹는 최대의 사탕수라고 정의를 한 뒤 제출을 하니까 WA를 받았다. 다시 잘 생각해보니 l~r을 커버할 때 나머지 구간에 사라진 사탕수가 항상 최적으로 있을 수 없다는 걸 깨달았다. 따라서 dp테이블의 정의를 바꾸어 l에서 r까지 구간을 커버하고 사라지는 사탕 수로 문제를 풀어야한다. 근데 이 또한 사라지는.. 더보기 BOJ)2370 시장 선거 포스터 문제:icpc.me/2370 포스터를 붙이는 순서가 주어질 때 보이는 포스터의 수를 출력하는 문제이다. 포스터의 모든 x좌표와 y좌표를 좌표압축 한 뒤 포스터를 역순으로 보면서 이미 본 포스터는 업데이트 시켜주고 내가 보이는지 여부는 이미 업데이트 된 포스터들이 나를 완전히 가리는지 확인하면 된다. 이는 세그먼트 트리를 이용하여 업데이트 된 구간의 합을 찍어냄으로 판별 가능 하다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include #include using namespace std;int n, seg[80040], lazy[80040],.. 더보기 BOJ)3073 집으로 가는 길 문제: icpc.me/3073 집과 아이를 1:1 매칭시켜 주어야 하는데 매칭은 항상 보장되고 이때의 아이들의 최소 이동거리를 출력하는 문제이다. 1:1 매칭이 항상 보장되기 때문에 MCMF로 모델링을 하여 소스->아이->간선->집->싱크로 모델링 해주면 된다. 이 때 각 간선들의 cost를 1로 설정해주면 된다. 다만 문제에 함정이 있는데 언제 고쳐질지는 모르겠지만 입력 N,M이 20~30으로 표기되어 있지만 100 넘게 들어오는거 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879.. 더보기 이전 1 ··· 15 16 17 18 19 20 21 ··· 118 다음