백준 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.
백준 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.