백준 32291번 - x와 x+1의 차이(증명 포함, C++)
문제백준, 실버 1, https://www.acmicpc.net/problem/32291풀이 날짜: 2025.4.15.풀이 시간: 10:49~11:32(43분)사용 언어: C++문제 해설해당 문제는 (x+1)의 자신을 제외한 약수를 구하는 문제이다.우선, 그에 도달하는 과정을 살펴보자.예제 1의 출력을 보면, x = 998일 때 x+1의 자신을 제외한 약수 1, 3, 9, 27, 37, 111, 333이 정답이 된다.이를 보고 출력이 되는 모든 양의 정수 k는 (x+1)의 약수라고 가설을 세울 수 있다.왜 k는 반드시 (x+1)의 약수인가?가설을 세웠으니 증명해 보자.다만 고등학생 때 배웠던 귀류법을 가지고 야매로 증명했다 보니, 정확하지 않을 수 있다는 점 양해 바란다. 잘못된 점이 있다면 지적해주면 ..
2025. 4. 15.
백준 10897번 - Inherited disease(C++)
문제백준, 골드 5, https://www.acmicpc.net/problem/10897풀이 날짜: 2025.4.9.풀이 시간: 2시간 가량알고리즘 분류: 수학, 구현, 트리사용 언어: C++문제 해설d번째 세대의 인원 수는 d!이며 세대 d ≤ 100이므로, 트리를 직접 만들어서는 해결할 수 없다.따라서 수학적으로 해결해야 한다.몇 번의 실험 후, 다음과 같이 식을 세웠다.l 세대 c번째 자손의 번호 F(l, c)는F(l, c) = [1번째부터 (l-1)세대까지 정민의 수] + [(l-1) 세대에서 ‘현재 선택된 부모’의 손위 형제의 수] * l + c와 같이 정의할 수 있다.(다만, F는 이전 입력에 따라 바뀌므로 엄밀히 말하면 함수라고 할 수는 없다.)예를 들어, 예제 입력에서31 2 1출력은 0번..
2025. 4. 9.
백준 13460번 - 구슬 탈출 2
1. 문제백준, 골드 1, https://www.acmicpc.net/problem/13460풀이 날짜: 2025.3.21.풀이 시간: 10:52~12:24(1시간 32분)알고리즘 분류: 구현, 그래프 탐색, 시뮬레이션, 너비 우선 탐색(BFS)사용 언어: C++2. 문제 해설상, 하, 좌, 우로 이동시킨다는 것은, 위쪽, 아랫쪽, 왼쪽, 오른쪽으로 옮겼을 때에 대한 가능성 트리 노드를 순회하는 것과 같다고 생각할 수 있다.그러면 해당 문제는 이동횟수를 최소화하는 최단 경로 그래프 탐색 문제로 생각할 수 있으므로, 간선의 개수가 이동 횟수인 지금은 BFS를 통해서 탐색하면 된다.탐색할 수 있는 경우의 수는 4가지이고 깊이는 최대 10이므로(10회보다 더 이동할 경우 탐색하지 않음), 경우의 수는 $4^{..
2025. 3. 21.
