백준 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.
백준 2075번 - N번째 큰 수: 약간 더 빠른 코드
문제백준, 실버 3, https://www.acmicpc.net/problem/2075풀이 날짜: 2025.2.4.풀이 시간: 11:03~11:29(26분)알고리즘 분류: 정렬, 우선순위 큐사용 언어: C++문제 해설해당 문제는 상위 N번째 값을 구하는 문제이지만 두 가지 특징이 있다.메모리 제한이 걸려 있다. 12MB의 제한이 있다.모든 수는 자신의 한 칸 위의 수보다 더 크다.첫 번째 특징을 생각해보면, 해당 문제는 NN (1≤N≤1500)의 보드가 주어지고 각 값의 절댓값이 10억보다 낮으므로 자료를 모두 저장하는 데에 최소 1,5001,5004Byte=2,250,0004Byte = 9,000,000Byte, 즉 약 9MB의 메모리가 필요하다.이것만 해도 메모리 제한이 아슬아슬하므로, 만약 정렬을 ..
2025. 2. 4.
