괴물 클럽

CF577B: Modulo Sum 주어진 수열에서 연속되지 않은 부분 수열을 선택하여 그 합이 특정 수 m으로 나누어 떨어지는지 판단하는 문제입니다. 해결의 핵심은 비둘기집 원리 (Pigeonhole Principle) 에 있습니다. 수열의 길이 n이 모듈로 값 m보다 크다면,PREFIX 합을 m으로 나눈 나머지는 총 m가지 경우しか 존재하지 않습니다. 따라서 n > m인 상황에서는 반드시 같은 나 ...

1. 정수 합 구성 문제 (2022) 서로 다른 10 개의 양정수를 선택하여 그 합이 2022 가 되는 경우의 수를 구하는 문제입니다. 이는 제한 조건이 두 개 존재하는 배낭 문제 변형으로 볼 수 있습니다. 접근 방식 1 부터 2022 까지의 숫자를物品으로 간주합니다. 각 숫자는 그 자체의 값을 비용 (weight) 으로 가지며, 선택된 숫자의 개수도 제한 조건이 됩니다. 따라서 상태 공 ...

A - 윤년 계산 문제 요약 입력으로 받은 연도 n을 기준으로 해당 연도의 일수가 365 일인지 366 일인지 판단해야 합니다. 해결책 윤년 여부를 판별하는 논리식을 적용하면 됩니다. 일반적으로 다음 규칙이 성립합니다: 4 로 나누어 떨어지지 않는 경우 평년입니다. 400 으로 나누어 떨어지는 경우 윤횔입니다. 100 으로 나누어 떨어지지 않으면서 4 로 나누어 떨어지는 경 ...

A - Shik and Stone 시작점 \((1, 1)\)에서 경로를 시뮬레이션하며 이동하면 된다. #include <bits/stdc++.h> using namespace std; const int MAX_N = 15; string grid[MAX_N]; bool visited[MAX_N][MAX_N]; int main() { int rows, cols; cin >> rows >> cols; string padding(cols + 2, '.'); grid[0] = grid[rows + 1] = pad ...

이번 라운드의 A~G번 문제에 대한 핵심 아이디어와 구현 방법을 정리합니다. A. Don't Try to Count 문자열 t가 s의 연속 부분문자열이 되도록 만드는 문제입니다. s를 반복하여 이어붙이면 길이가 2배로 늘어나는 특성을 활용합니다. n·m ≤ 25 조건 덕분에 최대 5번만 반복하면 충분합니다. #include <bits/stdc++.h> using namespace std; bool isSubstr(const s ...

문제 정의 두 개의 문자열 source와 target이 주어질 때, source가 target의 부분 수열(subsequence)인지 판별하라. 두 문자열은 모두 소문자 알파벳으로 구성된다. 부분 수열은 원본 문자열에서 일부 문자를 제거하되(0개도 가능), 남은 문자의 상대적 순서를 유지하여 만들 수 있는 문자열이다. 예를 들어 "ace"는 "abcde"의 부분 수열이지만 "aec"는 아니다. 확장 시나 ...

배낭 문제와 동적 계획법 대부분의 배낭 문제들은 01 배낭으로 변환한 후 복잡도를 최적화하는 방식으로 접근한다. 01 배낭 문제 각 물건은 선택하거나 선택하지 않는 두 가지 경우만 존재한다. 0과 1의 관계에 해당하기 때문에 01 배낭이라고 명칭한다. dp[i][j]를 앞에서부터 i개의 물건 중容量 j의 배낭이 담을 수 있는 최대 가치라고 정의하자. i번째 선택지는 i- ...

[NOI2025 예선 R1] A - 기본 사이클 구조 다음의 수학적 원리를 활용한다: Cayley 정리 n개의 노드가 k개의 연결 성분으로 구성되어 있을 때, 이들을 연결하기 위해 k-1개의 간선을 추가하는 방법의 수는 n^(k−2) × ∏(i=1 to k) size_i이다. 이 정리를 바탕으로, 입력 그래프에 이미 사이클이 존재하는 경우 답을 직접 계산할 수 있다. 반면, 초기 상태에서 사이 ...

기본 배낭 문제 배낭의 최대 용량과 다양한 무게 및 가치를 가진 아이템들이 주어졌을 때, 배낭에 담을 수 있는 최대 가치를 구하는 문제입니다. 문제 설명 첫째 줄: 두 정수 M(배낭 용량)과 N(아이템 개수) 둘째 줄부터 N+1번째 줄까지: 각 아이템의 무게와 가치 출력: 배낭에 담을 수 있는 최대 가치 예시 입력 10 4 2 1 3 3 4 5 7 9 예시 출력 12 ...

P1352 상사 없는 파티 트리에서 인접한 노드를 동시에 선택할 수 없는 상황에서 최대 가중치 합을 구하는 문제입니다. 상태 정의: val[node][0/1] - 현재 노드를 포함하지 않는 경우(0) 또는 포함하는 경우(1)의 하위 트리 최대값 점화식: val[node][1] = weight[node] + Σ val[child][0] (현재 노드를 선택하면 자식들은 선택 불가) val[node][0] = Σ max(val[child][0], ...