본문 바로가기

2017/08

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.. 더보기
BOJ)2104 부분배열 고르기 문제: icpc.me/2104 주어지는 배열에서 i~j까지의 부분 배열을 선택했을 때 (a[i]+a[i+1]+...+a[j])*(min(a[i],a[i+1]),....,a[j]) 가 최대가 되도록 i j를 선택하는 문제이다. 나이브한 풀이법으로는 i,j를 선택하는데만 O(N^2)으로 시간초과다 .. 따라서 좀 더 그리디하게 생각해보면 만약에 어떤 구간에 대해 정할 때 한 점 X를 기준으로 그 점이 최솟값이 되게 구간을 선택한다면 X를 기준으로 좌우로 최대한 X보다 큰값을 가지는 범위롤 포함하도록 배열을 선택할 수 있다. 이러한 아이디어에서 출발하여 모든 점에 대해서 이 범위를 볼건데 정렬을 해주어 작은 값부터 보면서 set에 업데이트해주어 이동가능한 lower_bound와 upper_bound를 찾아준다.. 더보기
뒤늦은 제 3회 SCPC 후기 목요일에 SCPC가 끝났다. 사실 그렇게 큰 기대를 하고 가지는 않았지만 혹시 모를 행운을 위해 플로우쪽을 준비를 해갔지만 아쉽게도 플로우 문제는 나오지 않았다 ㅠㅠ 본선에는 총 4문제가 나왔는데 1번 문제는 정말 쉬운 문제가 나왔다. 그래서 거의 시작하자마자 곳곳에서 타자소리로 어수선해졌다. 1번 문제를 빠르게 해결하고 2번 문제를 보자마자 좌절했다.. 기하라니 .. 점과 직선사이의 거리를 n^2으로 탐색하는 솔루션은 알 수 있었지만 그 이상으로 발전시키기도 힘들었고 기하는 라이브러리로만 만들어 놨지... 벡터에 관련 된 공식들이 가물가물해서 C번을 먼저 보기로 했다. C번을 보고 미디움 솔루션이 바로 떠올라서 코딩을 했다 (long long을 사용안한 초보적인 실수때매 2번이나 틀린건 비밀..) 이제.. 더보기
BOJ)2872 우리집엔 도서관이 있어 문제: icpc.me/2872 책의 순서가 주어졌을 때 책을 정렬하는데 필요한 최소 이동횟수를 출력하는 문제이다. 책을 이동하는 조건은 무조건 하나의 책을 들어서 맨위에 쌓는 방법밖에 없기 때문에 가장 뒤에 있어야 하는 책은 옮길 필요가 없다. 가장 큰 숫자부터 연속 된 숫자가 얼마나 긴 부분 증가 수열을 이루고 있는지 확인하면 된다. 1234567891011121314#include #include using namespace std;int n, a[300030], here;int main() { scanf("%d", &n); for (int i = 0; i = 0; i--) if (a[i] == here)here--; printf("%d\n", here); return 0;}Colored by Col.. 더보기
BOJ)10272 현상금 사냥꾼 김정은 문제:icpc.me/10272 왼쪽 부터 오른쪽으로 순회한 뒤 순회하지 않은 정점들을 오른쪽에서 왼쪽으로 다시 순회할 때 이동거리의 최솟값을 구하는 문제이다. 이 문제는 바이토닉 투어 문제이므로 N^2 다이나믹 프로그래밍으로 해결할 수 있다. 우선 바이토닉 투어 문제는 dp[x][y]라는 테이블을 세울 수 있다. 이 때 x.는 갈 때 y는 올 때 까지 커버한 정점들의 수 이다. 점화식을 세울 때 현재 x,y까지 커버했다면 다음에 커버해야 할 정점은 당연히 max(x,y)+1이 되므로 이 정점을 갈 때 커버할 지 올 때 커버할지만 결정해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738#include #include #inc.. 더보기
L-R flow http://blog.myungwoo.kr/111 와 http://koosaga.com/134 에서 많은 부분 참고하였습니다. -간선에 lower_bound가 존재할 때 플로우를 흘릴 수 있는지 여부 확인 1. MCMF로 모델링 a->b로의 간선이 하한이 l 상한이 r일 때 a->b로 (l , -1) , (r-l ,0)으로 두가지 간선을 만들어 준 뒤 MCMF 를 돌린다면 항상 -1이 있는 쪽으로 플로우가 강제된다. 이 때 cost를 확인하여 플로우를 흘릴 수 있는 지 여부를 확인해준다. 이 때의 maxflow는 flow를 확인하여 구할 수 있다. 2. 디닉을 사용하는 방법 새로운 소스와 새로운 싱크를 만든다. 기존 싱크-> 기존 소스로 capacity가 INF인 간선을 생성한다. a->b로의 간선이 하.. 더보기
BOJ)8462 배열의 힘 문제: icpc.me/8462 시퀀스와 쿼리가 주어질 때 매 쿼리에 대한 답을 출력하는 문제이다. 쿼리는 구간이 주어지면 구간에 존재하는 모든 자연수 s에 대하여 (s 의 개수의 제곱) x s를 합한 값이다. 쿼리와 시퀀스가 10만이기 때문에 적어도 쿼리를 log나 root 시간에 처리해주고 싶지만 안타깝게도 저 쿼리를 해당 시간에 처리하기는 힘든거 같다. 하지만 쿼리 도중에 업데이트가 일어나지 않기 때문에 쿼리를 정렬한 뒤 mo's 알고리즘으로 접근한다면 해답을 얻을 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include usin.. 더보기
BOJ)3172 현주와 윤주의 재미있는 단어 게임 문제:icpc.me/3172 어떤 단어가 x가 어떤 단어 y보다 사전순으로 앞서 있으면서 y를 뒤집은 y'이 x를 뒤집은 x'보다 앞서 있다면 두 단어는 서로 좋아하지 않는다고 한다. 단어가 10만개이기 때문에 brute force로 접근한다면 시간초과를 면치 못할 것이다. 그렇기 때문에 생각을 바꾸어서 기존의 문자열 기준으로 정렬을하여 번호를 매겨준 뒤 그 번호를 가진 상태로 문자열을 다 뒤집은 후 정렬을 해주고 앞에서 부터 보면 나보다 먼저 본 문자열 중에 나보다 할당 된 번호가 큰 문자열의 수를 세주면 된다. 이는 세그먼트 트리나 펜윅 트로로 효율적으로 해결할 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839#in.. 더보기

티스토리툴바