hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

문제 정보 링크: https://www.acmicpc.net/problem/11693 난이도: Gold II 분류: [수학 → 정수론] [분할 정복 → 분할 정복을 이용한 거듭제곱] 문제 요약 \( N^M \)의 약수의 합을 구하면 됩니다. 정말 정직하죠? 풀이 \( N \)을 소인수분해한 결과가 아래와 같다고 합시다. \( N = p_{1}^{e_{1}} \times p_{2}^{e_{2}} \times \ldots p_{k}^{e_{k}} \) 그럼 \( N^M \)을 소인수분해한 결과는 자명히 아래와 같게 됩니다. \( N^M = p_{1}^{Me_{1}} \times p_{2}^{Me_{2}} \times \ldots p_{k}^{Me_{k}} \) 지금부터는 이 \( Me_{i} \)를 편의상 ..

문제 정보 링크: https://www.acmicpc.net/problem/15655 난이도: Silver III 분류: [재귀 → 백트래킹] 문제 요약 \( N \)개의 수가 주어질 때, \( M \)개를 중복없이 선택해서 만들 수 있는 모든 조합을 찾으면 됩니다. 풀이 오름차순으로 정렬된 수열을 출력해야 하니, 들어온 수들을 오름차순 정렬해봅시다. 이제 남은 건 백트래킹으로, \( M \)개를 "중복 없이" 고르는 걸 시뮬레이션해주면 됩니다. 이는 "마지막으로 선택한 원소의 위치"를 저장한 뒤, 이보다 더 오른쪽에 있는 원소만을 골라주면 됩니다. int n, m; int arr[10]; int res[10]; void btk(int cnt, int idx){ if (cnt == m){ for (int..

문제 정보 링크: https://www.acmicpc.net/problem/11813 난이도: Platinum I 분류: [자료구조 → 분리 집합 (DSU) → Small to Large] [오프라인 쿼리] 문제 요약 트리 \( T = (V, E) \)가 주어질 때, (초기 상태를 포함해) 간선을 하나씩 자를 때마다 아래 문제의 답을 출력하면 됩니다. 임의의 두 정점 \( v \neq w \)에 대해, \( v \)에서 \( w \)로 가는 경로에 속한 간선들의 가중치를 XOR한 값이 0인 정점쌍 \( (v, w) \)의 개수. (\( (v, w)\)와 \( (w, v) \)는 같은 것으로 취급한다.) 풀이 간선을 자르기만 합니다. 보통 이럴 때 하는 건 '쿼리를 역순으로 처리하면서 간선을 잇기'가 되죠..

문제 정보 링크: https://www.acmicpc.net/problem/16139 난이도: Silver I 분류: [누적합] 문제 요약 문자열 \( S \)에서 \( \alpha \)라는 알파벳이 \( [L, R] \) 구간 내에서 총 몇 번 등장하는지 묻는 문제입니다. + 쿼리 문제로, \( [L, R], \alpha \)가 바뀝니다. 서브태스크 1 (50점) 직접 \( [L, R] \) 구간을 돌리면서 \( \alpha \)의 등장 횟수를 세면 됩니다. 시간복잡도는 \( O(Q|S|) \)회입니다. void Main(){ string s; cin >> s; int q; cin >> q; while (q--){ char ch; int l, r; cin >> ch >> l >> r; int ans =..

문제 정보 링크: https://www.acmicpc.net/problem/15372 난이도: Bronze III 분류: [수학 → 사칙연산] 문제 요약 \( N \)이 주어졌을 때, \( N^2 \)의 배수인 가장 작은 \( K \)를 찾는 문제입니다. 풀이 \( N^2 \)의 배수 중 가장 작은 수는 당연히 \( N^2 \)입니다. 그러니 \( N^2 \)을 출력해주면 됩니다. 시간복잡도는 \( O(T \times 1) \)입니다. 코드 void Main(){ int t; cin >> t; while (t--){ ll n; cin >> n; cout