돌이 코딩하는 방

문제 링크 : https://www.acmicpc.net/problem/9446 문제 태그 더보기 DP,정렬 문제 소개 모든 물건을 각 가격에 살 수 있다. 하지만, 조합식에 따라서 두 물건을 합쳐 새로운 물건을 만들 수도 있다. 이때 1번물건을 만들기 위해서 필요한 최소가격을 구하자. 문제 풀이 문제를 보고 DP가 생각이 났다. DP table 정의도 바로 DP[i]=i번째 물건을 얻는 데 필요한 최소 비용. 또한 식은 i,j로 k를 만들 때 $DP[k]=min(DP[k],DP[i]+DP[j])$로 업데이트를 할 수 있다. 여기서 DP의 필요조건을 생각해보자. 어떤 DP table을 채울 때 사용되어진 값들이 있다면 그 사용되어진 값들은 확정된 상태여야 한다. 즉, 위의 식으로 따지면 DP[k]의 최종..

문제 태그 : https://www.acmicpc.net/problem/4002 문제 태그 더보기 Segment Tree 문제 소개 문제를 이해하기가 굉장히 어려웠다. 간단하게 설명을 하자면 트리에서 임의의 노드 x를 고른다. 그 후 x의 서브트리에서 몇 개의 노드를 고른다. 이때 노드의 비용의 합이 m이하가 되게 골라야 한다. 이때 고른 노드의 갯수와 x의 가중치의 곱의 최댓값을 구하는 문제이다. 문제 풀이 관찰 1. x가 정해진 상황에서 x의 서브트리에서 어떤 노드들을 골라야 할 때 결국은 갯수만 중요하기 때문에 당연하게도 비용이 낮은 것부터 선택을 해야한다. 즉 greedy 하게 고를 수 있다는 것이다. 이를 바꿔서 생각하면 비용이 많은 것부터 사용하지 않을 것이다. 관찰 2. 이를 트리의 노드 사..

문제 링크 : https://www.acmicpc.net/problem/2415 문제 소개 좌표평면에 점들이 주어지면 주어진 점들로 만들 수 있는 가장 큰 직사각형의 크기를 출력하는 문제이다. 문제 풀이 굉장히 아이디어성 문제이고, 다양한 풀이가 나올 수 있는 문제이다. 일단 이 문제를 풀기 위해서 직사각형의 성질들을 생각해보자. - 두 쌍의 대변의 길이가 각각 같다. - 두 쌍의 대각의 크기가 각각 같다. - 두 대각선이 서로 다른 대각선을 이등분 한다. - 두 대각선의 길이가 같다. 한 직사각형에서 변이나 길이는 두 쌍이지만, 대각선은 두 개이다. 따라서 대각선에 집중을 해보자. 두 대각선의 길이가 같고, 서로 이등분하면 직사각형이다. 즉, $N^2$개의 선을 만들 수 있고, 그 중 길이가 같고 서로..

문제 링크 : https://www.acmicpc.net/problem/13209 문제 태그 더보기 Parametric Search 문제 소개 트리가 있다. 이중 k개의 간선을 끊어서 k+1개의 트리로 만든다. 이때 각 트리에 포함된 노드의 가중치의 합들 중 최댓값의 최솟값을 구하시오. 문제 풀이 트리의 간선을 '최대한 잘' 끊어야 한다. 트리별로 노드의 가중치의 합이 최대한 비슷하도록, 어느한쪽이 치우치지 않도록 끊어야 한다. 어떻게 해야 최대한 잘 끊을 수 있을까? 이를 생각하는 문제는 굉장히 어렵다. 너무 다양한 경우의 수가 나오게 된다. 따라서 좀 다른 방식을 생각해보자. 트리에서 어떻게 잘 잘라서 "가능한 최솟값"을 물어보는 문제이다. x가 된다면 당연히 x이상은 모두 다 가능하고, x가 불가능..

문제 링크 : https://www.acmicpc.net/problem/13548 문제 태그 더보기 Mo's algorithm 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 가장 많이 등장하는 수가 몇 번 등장했는지 출력한다. 문제 풀이 일단 문제를 읽어보자. 구간 내에서 가장 많이 나타나는 수 -> 각각의 수들이 몇번씩 나왔는지 관리하려고 하면 된다. 또한 이 질문이 쿼리로 주어진다. 이러한 형식의 문제를 많이 풀어봤으면 바로 Mo's algorithm을 써야 한다는 생각을 할 수 있다. Mo's algorithm 으로 구간을 더하거나 빼주면서 각 숫자별로 몇 개씩 있는지 관리한다고 생..

문제 링크 : https://www.acmicpc.net/problem/13547 문제 태그 더보기 Mo's algorithm 문제 소개 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. 문제 풀이 수의 갯수를 출력하기 위해서는 수들의 집합을 관리 해야한다. 쿼리로써 구간을 많이 주는데 그 쿼리마다 수들의 집합을 관리해야한다 -> 바로 Mo's algorithm을 떠올릴 수 있다. 풀이도 꽤나 간단하게 보인다. Mo's algorithm을 이용하여 구간을 정렬하고 구간내에서의 각 숫자의 갯수를 세주면 된다. 구간을 추가할 때는 추가되는 구간의 숫자의 갯수에 1..

BOJ 2512 고등부 1번 예산 문제 링크 : https://www.acmicpc.net/problem/2512 문제 태그 파라매트릭 서치, 이분 탐색 문제 풀이 설정 할 수 있는 (가능한) 가장 큰 값을 묻는 문제이다. 이 부분을 보자마자 바로 파라메트릭 서치를 한 번 떠올려야 한다. 내가 어떤 값을 제사하여 그 값이 가능한가? 로 묻는 문제로 바꾸면 훨씬 더 쉽게 해결할 수 있을지에 대해 생각하면 파라메트릭을 쓸지에 대한 여부가 결정되고, 따라서 이 문제는 쓰는 것이 좋다. 더이상 말이 크게 필요없다. 지난번 글에서도 썻듯이 파라메트릭 서치 기본 문제이다. 코드 더보기 #include #include typedef long long ll; using namespace std; ll n, a[1000..

문제 링크 : https://www.acmicpc.net/problem/13546 문제 태그 더보기 Mo's algorithm 문제 소개 1보다 크거나 같고, K보다 작거나 같은 수로 이루어져 있는 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. l r: max{|x − y| : l ≤ x, y ≤ r and $A_x$ = $A_y$} 을 출력한다. 문제 풀이 일단 각 쿼리의 구간내에서 각 숫자별로 그 숫자들이 존재하는 위치들을 전부 알고 있어야 쿼리의 질문에 대한 답을 구할 수 있다. "구간 별로 숫자의 집합을 관리한다." 는 Mo's algorithm을 통해서 해줄 수 있다. deque 를 숫자 범위의 갯수만큼 만들어서 각 deque별로 ..

문제 링크 : https://www.acmicpc.net/problem/13554 문제 태그 (관련 지식) 더보기 Mo's algorithm, Segment tree 문제 소개 길이가 N인 두 수열 A1, A2, ..., AN과 B1, B2, ..., BN가 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: i ≤ p, q ≤ j이면서 Ap × Bq ≤ k 인 (p, q) 쌍의 개수를 출력한다. 문제 풀이 일단 오프라인 쿼리고 시간제한이 6초이다. 사실 어떻게 접근을 해야할지 모르겠다. 이 문제를 볼 때 쯤이면 다른 수열과 쿼리 문제를 꽤나 풀어봤을 것이고, 그러면 수쿼를 풀 수 있는 도구중 Mo's Algorithm이 생각이 날 수 밖에 없다. 하지만 문제가 있다. Mo's a..

문제 링크 https://www.acmicpc.net/problem/14435 문제 소개 놀이기구가 주어지고, 각 놀이기구에 같이 탈 두명이 각각 주어진다. 그 둘이 놀이기구를 타기 위해서는 둘의 키의 합이 제한을 넘어야 한다. 각 날마다 한 명의 키가 1씩 크며 전날에 제한을 만족한 놀이기구가 그 전날 제한을 만족한 놀이기구 수 보다 많다면 키가 1이 더 큰다. 이때 각 날 별로 몇 개의 놀이기구에 대하여 아이들이 제한을 만족하는지 출력하여야 한다. 문제 풀이 굉장히 재밌는 아이디어의 문제였고, 이 문제를 혼자 생각하지 못하였다. 거의 모든 부분을 이해한 업솔빙 느낌의 문제였다. 그래서 만약 처음부터 생각했다면 어떤 느낌으로 접근해야 맞을지를 생각하여 작성하였다. 일단 $O(QK)$의 풀이를 생각해보자..