문제 링크https://www.acmicpc.net/problem/32068 문제 요약이 문제는 시작점 \(S\)에서 출발하여 보물 위치 \(L\) 또는 \(R\)에 방문하는데 필요한 이동 횟수를 계산하는 것이다. 이동 패턴은 한 단계식 오른쪽과 왼쪽을 번갈아가며 한 칸씩 점점 더 멀리 이동하는 방식이다. 문제 풀이서브태스크 4번까지는 입력 제한이 크지 않아 시뮬레이션으로도 해결할 수 있다. 그러나 서브태스크 5번을 해결하려면 더 효율적인 접근 방법이 필요하다. 먼저, \(S\)보다 왼쪽에 있는 \(L\)을 방문하기 위해서는 \(S\)와 \(L\)의 거리만큼 떨어진 오른쪽에 있는 점들을 모두 방문해야 한다. 따라서 \(L\)을 방문하기 위한 이동 횟수는 \(2 \times (S - L)\)이다. 마찬가지..
문제 링크https://www.acmicpc.net/problem/32036 문제를 바꿔서 생각하기배열에 연산을 직접 하는것이 아니라 수학적인 방법으로 접근하면 조금 더 쉽게 문제를 해결할 수 있다. 1번 쿼리에서 주어지는 a, b를 아래와 같이 함수로 표현될 수 있다.(문제에서는 x, y라고 했는데, 좌표 평면에서의 x, y와 겹치기 때문에 헷갈리지 않기 위해 a, b로 바꿔서 적었다.)$$f_i(x) = |x - a_i| + b_i$$주어진 여러 개의 1번 쿼리를 통해 업데이트된 배열의 값은 각 1번 쿼리의 함수들을 더한 것으로 표현될 수 있다.$$F(x) = \sum_{i=1}^{n} f_i(x) = \sum_{i=1}^{n}|x - a_i| + \sum_{i=1}^{n} b_i$$2번 쿼리에서는 ..
문제 링크https://www.acmicpc.net/problem/31997 문제 요약N명의 사람들이 T시간 동안 진행되는 회의에 참석하고 떠나는 시간이 주어진다. 그리고 각 사람들은 서로 친구 관계를 맺고 있다. 회의가 진행되는 동안 특정 시각 t에서 회의에 참석한 사람들 중 친구인 쌍이 몇 쌍인지 계산하는 문제이다.. 문제 풀이입력 데이터 처리N명의 사람들이 언제 도착하고 떠나는지, 그리고 누구와 친구 관계를 맺고 있는지 저장해야 한다. 각 시간마다 어떤 사람이 회의에 참석하고 떠나는지를 기록하면, 회의가 진행되는 모든 시간 동안 현재 참석하고 있는 사람들을 쉽게 파악할 수 있다. 또한, 친구 관계는 인접 리스트를 이용해 저장한다.// 각 시간대별로 회의에 참석하는 사람을 저장할 벡터vector> i..
문제 링크https://www.acmicpc.net/problem/31965 피로도를 최소로 하는 회의 순서 정하기회의 세트에 참여하는 K개의 집의 좌표를 오름차순으로 \(x_1, x_2, \cdots, x_k\)라고 하고, 각 집에서 회의를 개최했을 때 드는 비용을 \(c_1, c_2, \cdots, c_k\)라고 정의하자. 각 집에서 회의를 개최했을 때 드는 비용을 계산한 뒤 유심히 관찰해 보면, 회의 비용이 감소하거나 증가하는 방향으로 회의를 개최할 때 피로도가 최소가 된다는 것을 발견할 수 있다. 그 이유는 회의 비용이 정렬되어 있으면 인접한 회의의 비용 차이를 최소화할 수 있기 때문이다. 회의 비용이 정렬되어 있을 때 피로도는 \(c_1, c_2, \cdots, c_k\)중에서 최댓값과 최솟값의..
문제 링크https://www.acmicpc.net/problem/31964(KOI 2024 1차대회 초등부 3번, 고등부 1번) 문제 요약트럭이 직선 도로상의 각 집을 특정 시각 이후에 방문에 물건을 회수한 후 다시 출발지로 돌아올 수 있는 최단 시간을 구하는 문제이다. 문제 풀이그리디로 접근하기출발지점에서 마지막 집까지 왕복하는 거리인 \(2 \times X_n\)은 트럭이 필수적으로 사용해야 하는 시간이다. 따라서 이 시간을 제외하고 각 집에서 기다려야 하는 시간을 최소화하는 것이 중요하다. 오른쪽 끝 집부터 방문해 물건을 회수하면, 트럭이 출발지점으로 돌아오는 시간에 각 집에서 기다려야 하는 시간이 포함될 수 있다. 그래서 트럭이 가장 오른쪽 집부터 방문에 물건을 회수하는 것이 가장 최선의 선택지..
문제 링크https://www.acmicpc.net/problem/31963(2024 KOI 1차대회 초등부 2번, 중등부 1번) 문제 요약길이가 N인 수열이 주어졌을 때, 수열의 한 원소에 숫자 2를 곱하는 연산을 할 수 있다. 이때 주어진 수열을 오름차순으로 만들 수 있는 최소한의 연산 횟수를 구하는 문제이다. 문제 풀이시뮬레이션으로 문제 풀기(부분점수)수열의 두 번째 원소부터 마지막 원소까지 순회하면서, 각 원소가 이전 원소보다 커질 때까지 2를 곱하는 과정을 반복하고, 그 횟수를 직접 계산하는 방법으로 문제를 풀 수 있다.int simulate(const vector& vi) { vector incresing_order(vi.size()); incresing_order[0] = vi[..
문제 링크https://www.acmicpc.net/problem/16937 문제 요약모눈종이 안에 두 개의 스티커를 겹치지 않게 붙일 때, 그 넓이의 합의 최댓값을 구하는 문제이다. 문제 풀이N의 크기가 작기 때문에 문제를 해결하기 위해 완전탐색을 사용할 수 있다. 따라서, 두 개의 스티커를 골라 모눈종이 안에 붙일 수 있는지 판단하는 함수를 작성하는 것이 이 문제를 해결하기 위한 핵심이다. 1. 첫 번째 스티커 붙이기먼저, 한 개의 스티커를 모눈종이 안에 붙일 수 있는지 판단하는 함수인 isInside 함수를 작성한다. 이 함수는 왼쪽 사각형이 오른쪽 사각형을 포함할 수 있는지 판단한다. 왼쪽 사각형의 가로와 세로가 오른쪽 사각형의 가로와 세로보다 같거나 큰지 확인하는 것으로 구현할 수 있다.boo..
문제 링크https://www.acmicpc.net/problem/30804 문제 요약1부터 9로 이루어진 수열이 주어진다. 이때, 연속된 부분 수열 중에서 숫자가 최대 두 개의 숫자로만 이루어진 부분 수열의 최대 길이를 구하는 문제이다. 문제 풀이이 문제를 푸는 가장 효율적인 방법은 슬라이딩 윈도우 기법을 이용하는 것이다. 하지만 문제에서 주어진 제약 조건들을 잘 활용하면 조금은 더 간단한 방법으로 문제를 해결할 수 있다. 이 문제가 Division 1, Division 2에 동시에 출제된 것을 보면 다양한 접근 방법을 생각할 수 있게 의도된 문제로 보인다. 문제의 제약 조건을 활용하면 더욱 효과적이고 빠른 해결 방법을 찾을 수 있기 때문에, 문제를 풀기 전에 제약 조건을 먼저 확인하는 것이 중요하다..
문제 링크https://www.acmicpc.net/problem/17845 문제 요약최대 공부시간 \(N\)과 과목 수 \(K\)가 주어진다. 이어서 각 과목 \(i\)의 중요도 \(I_i\)와 필요한 공부시간 \(T_i\)가 주어진다. 최대 공부시간 \(N\)을 초과하지 않으면서 중요도 합이 최대가 되도록 과목을 선택할 때, 최대 중요도를 구하는 문제이다. 문제 풀이이 문제는 전형적인 배낭 문제(Knapsack Problem)로 동적 계획법(Dynamic Programming)을 이용해 풀 수 있다. 동적 계획법은 Top Down 방식과 Bottom Up 방식으로 풀 수 있는데, 여기서 두 가지 방법 모두를 이용해 문제를 푸는 방법을 소개한다. Top Down 방식으로 문제 풀기동적 계획법을 Top ..
Prefix Sum 알고리즘이란?문제를 풀다 보면 배열에서 특정 구간의 합을 구해야 하는 문제들을 종종 만나곤 한다. 한 번만 계산해야 한다면 반복문을 통해 \(O(N)\)의 시간 복잡도로 해결할 수 있지만, 여러 번 반복해서 계산해야 한다면 조금 더 효율적인 알고리즘이 필요하다. 이때 사용할 수 있는 알고리즘이 Prefix Sum이다. Prefix Sum 알고리즘은 배열의 첫 번째 원소부터 각 원소들까지의 합을 미리 계산해두는 알고리즘이다. 예를 들어, 배열 [1, 2, 3, 4, 5]가 있을 때 첫 번째 원소의 Prefix Sum은 1, 두 번째 원소의 Prefix Sum은 1 + 2 = 3, 세 번째 원소의 Prefix Sum은 1 + 2 + 3 = 6 이 된다. 이렇게 미리 배열의 모든 원소들의..
문제 링크https://www.acmicpc.net/problem/2417 문제 요약문제에서 주어진 N의 제곱근을 소수점에서 올림 한 값을 구하는 문제이다. 함정이 가득한 문제문제 자체는 상당히 간단해 이제 막 PS에 입문한 사람들이 연습용으로 풀기 좋은 문제로 보인다. 그리고 문제 번호도 2000번 대여서 뭔가 연습문제 같은 느낌도 상당히 든다.???: 제곱근을 수하고 소수점에서 올림을 하라니?! sqrt 함수를 이용하면 그냥 풀 수 있는 문제잖아! 이런 생각의 흐름을 거치고 나면 아래와 같은 코드를 작성하고 제출을 누르게 된다.#include #include using namespace std;int main() { unsigned long long n; cin >> n; ..
문제 링크https://www.acmicpc.net/problem/15989 문제 요약정수 N이 주어졌을 때, 1, 2, 3의 합으로 N을 나타내는 경우의 수를 찾는 문제이다. 순서만 다른 것은 같은 경우라는 것을 주의해야 한다. 문제 풀이이 문제는 전형적인 동적 계획법(dynamic programming, 이하 DP)로 해결할 수 있다. DP는 상향식과 하향식 두 가지 방법으로 구현할 수 있는데 보통은 하향식 방법이 구현이 쉽고 직관적이다. 하지만 슬라이딩 윈도우, 컨벡스 헐 트릭등 다양한 DP 최적화 전략을 이용하기 위해서라면 상향식 방법도 이용할 줄 알아야 하기 때문에 두 가지 방법으로 모두 구현을 해본다. 하향식으로 문제 풀기상향식으로 문제를 풀 때 가장 먼저 해야 할 일은 재귀적으로 문제를 해결..
