문제 한국정보올림피아드 2013년 고등부 1번 백준 8983번 풀이 사대의 위치와 동물의 위치 간의 거리는 x좌표의 차이와 동물의 y좌표를 더한 값입니다. 또한, 사대는 x축 위에 있기 때문에 y좌표는 어느 사대를 선택하던 변하지 않습니다. 즉, 동물과 가장 가까운 사대를 구하려면 x좌표의 차이가 최소가 되는 사대를 찾으면 됩니다. 동물의 수와 사냥꾼의 수가 최대 100,000이므로 각 동물에 대한 최적의 위치에 있는 사대를 찾을 때 완전 탐색을 하면 TLE가 납니다. 가장 가까운 사대를 찾기 위해 동물의 x 좌표에 대한 이분 탐색을 해봅시다. 이 때, lower_bound를 사용하는 경우 사대의 후보가 2개가 나옵니다. 이 경우에는 lower_bound로 선택된 사대가 정답입니다. 하지만 아래의 경우에..

문제 난이도는 솔브드 기준으로 1,2,3,4번 순서대로 브론즈 / 실버 / 골드 / 플레로 잘 배분된 것 같았습니다. ​1번은 정사각형의 변 길이를 2 ~ $ min(N, M) $ 잡고 삼중 for 돌리면 됩니다. 시간 복잡도는 $ O(N^3) $ 가 됩니다. ​2번은 투포인터 또는 분할 정복을 사용하면 됩니다. 비슷한 문제: https://www.acmicpc.net/problem/2003​​ 3번은 $ M $번째 쓰레기가 어디서 태워지는지 알아야하는데, 대부분 최소 공배수로 접근한 것 같습나다. 그리고 대부분이 못 푼 것 같습니다. TMI로 최소공배수를 사용한 접근 방법은 잘 모르겠으나 최소 공배수로 하면 소수(prime number)로 구성된 저격 테케를 만들면, 최소 공배수의 범위가 $ unsig..

문제 백준 5550번 풀이 전형적인 DP (누적합+그리디) 문제로 볼 수 있습니다. "dp[i] = i권을 선택했을 때 만들 수 있는 최대 가격" 으로 점화식을 세워줍시다. 모든 장르에 대해서 i번째 책까지 골랐을 때, 해당 장르의 j개의 책을 추가로 고르는 경우로 DP table을 채워주면 됩니다. 시간복잡도는 $ O(GN^2) $이 되는데, N이 1000이고 G가 10이므로 G는 무시할만한 수준입니다. 따라서, DP의 시간복잡도는 $ O(N^2) $이 됩니다. DP의 조건이 좀 까다로워 구현하는데 고생했던 것 같습니다. 소스코드 #include using namespace std; int dp[2001]; vector book[11], sum[11]; int main() { cin.tie(0)->sy..