본문 바로가기

백준

 (223)
백준 16225 - 제271회 웰노운컵 https://www.acmicpc.net/problem/16225 아이디어 우리는 저 숫자들을 괄호 집합으로 볼 것이다. 그러면 높은 합을 만들어내면서도 올바른 괄호 집합을 유지해야 하는 문제로 바뀐다. 문제를 보면 "내가 두 문제를 고르면 Etacoder Plus는 당연히 더 높은 B값을 가지는 문제를 가져갈 것이다."로 인해 B가 가장 높은 값은 Etacoder가 가져가고 B가 제일 낮은 값은 내가 가져감을 이해할 수 있다. 잘 이해가 가지 않는다면 곰곰히 생각해보자. 어떻게 해서든 내가 B가 제일 높은 값을 가져갈 수 없다는 사실을 깨우치면 이해할 수 있다. 그러면 주어진 pair 수열을 B의 오름차순으로 정렬하고 내가 가져가는 문제를 여는 괄호라 하고 상대가 가져가는 문제를 닫는 괄호라고 할 때..
백준 1437 - 수 분해 https://www.acmicpc.net/problem/1437 아마 이 글에 들어왔으면 같은 생각을 하고 있었을지도 모른다. "2 끼리 빼고 남는 거 3 만드는 게 최적해 아닌가?" 놀랍게도 아니다. 3씩 빼서 세제곱을 먹이는 게 더 커진다. 조금만 생각해도 제곱 증가량 < 세제곱 증가량인걸 눈치챌 수 있다. 아뿔싸! 따라서 3씩 빼다가 나머지가 1이면 하나를 4로 만들고, 나머지가 2면 2를 하나 만들어주는 식으로 전개한 뒤에 계산하면 최적해가 된다. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 4..
백준 1572 - 중앙값 https://www.acmicpc.net/problem/1572 전형적인 세그먼트 트리로 k번째 수를 찾는 쿼리를 이용하는 문제이다. 하지만 그 구현은 너무나도 귀찮다. C++을 사용하고 있다면 pbds를 이용해 간단하게 풀 수 있다. find_by_order와 order_by_key를 잘 이용하자. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 #pragma GCC target("sse..
[ICPC] 백준 3861 - Slalom https://www.acmicpc.net/problem/3861 아이디어 최단 경로는 변위가 작은, 다시 말해 가능한 한 회전을 하지 않을 때 성립한다. 조금 쉬운 예시로 다음 그림을 보면 좋다. 꺾지 않는 최장 직선 찾기 그러면 우리는 한 직선 이동에 게이트를 많이 지나는 방법을 찾아야 한다. 그러기 위해 우리는 다음 고려할 것이다. 어떤 게이트 끝점에서 직선으로 최대한 도달할 수 있는 게이트는 어디인가? 좀 더 생각하면 반드시 회전을 해야만 할 때 탐욕적으로 다음 게이트의 끝점에만 가면 됨을 알 수 있다. 이 사실을 통해 우리는 어떤 게이트의 끝점(시작점 포함)에서 출발할 때 다음 게이트의 끝점을 경유해야만 하는지, 그렇지 않아도 다음 게이트를 통과할 수 있는지 검사하면 충분하다는 생각을 할 수 있..
백준 22876 - 츠바메가에시 https://www.acmicpc.net/problem/22876 해당 문제는 공식 풀이에서 잘 설명하고 있으므로 이 포스트에서는 풀이 방법으로 제시된 indexed heap 풀이의 실 구현을 제공한다. Indexed heap에 대해서는 여기를 참조하라. 전체 코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 8..

티스토리툴바