본문 바로가기

백준 문제 풀이

 (134)
백준 11729번 하노이 탑 이동 순서 (C++) https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 하노이탑은 재귀문제에서 가장 기본적인 문제로 대학 강의에서 처음 배우게 된다. 그러나 나름 어려운 편이고 기본기를 정확히 하자는 의미로 하노이탑을 풀어봤다. 접근법 하노이 탑의 가장 기본적인 요소는 높이가 4인 하노이탑을 3번 막대로 옮기기 위해서는 맨아래 판을 제외하고 높이 3인 탑을 2번 막대로 옮기는 순서가 필요하다. 그러므로 Hanoi(4) -> Hanoi(3) 이렇게 포함이된..
백준 29792번 규칙적인 보스돌이 (C++) https://www.acmicpc.net/problem/29792 29792번: 규칙적인 보스돌이 보스의 체력 $P$의 제한 $2.66 \times 10^{11}$와 드랍하는 메소 $Q$의 제한 $1\,596\,506$은 2023년 8월 10일 업데이트 이전의 가장 많은 체력(카오스 혼테일)과 결정의 가격(노멀 파풀라투스)을 가진 일간 보 www.acmicpc.net - 접근법 이 문제는 다이나믹 프로그래밍 배낭문제이다. 그러나 캐릭터 1,2,3이 있다고 할 때, 1,2,3마다 dp를 돌려서 마지막 최댓값을 모두 저장해놓고 답을 도출하면 된다. 가장 중요한 건 배낭문제를 잘 이해하고 있느냐는 것이다. 배낭문제를 복기해보자. 최대 10kg 담을 수 있고 물건은 번호 무게 가치 1 4 6 2 2 7 3 5..
백준 15681번 트리와 쿼리 (C++) https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 접근법 - 먼저 그래프가 주어지고 이것의 루트가 주어진다. 그리고 트리를 구성하게된다. 그래프가 주어지고서 이것을 트리로 바꾸어야하기 때문에, 이것을 문제의 그림으로 표현하면 다음과 같다. 이 그래프에서 5를 루트라고 하였으므로 아래처럼 트리를 구성할 수 있다. 그리고 각 노드들의 서브트리의 노드 개수를 출력하면 된다. 이해하기는 쉽지..
백준 11438번 LCA 2 (C++) https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net LCA 공부를 열심히 하고서 풀이한 문제이다. LCA는 https://tigerfrom2.tistory.com/186 여기서 자세히 설명해두었다. 이 문제는 LCA1과 같은 문제지만 주어지는 노드의 수가 늘어났고, 시간이 더 타이트해졌다. LCA1은 조상을 탐색할 때 1씩 올라가며 탐색해도 AC를 받을 수 있었다. 그러나 이 문제는 dp를 활용하여 LCA를 개선하는 테이블을 미리 만들어둬..
백준 16562번 친구비(C++) https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 문제 해석을 잘못해서 어렵게 생각하고 있었다. 친구의 친구는 친구라고 해서 인접한 관계만 가능하고 한 칸 이상 떨어지면 안되는 것이라고 생각했다. 그래서 트리에서 다이나믹 프로그래밍을 진행했는데 정답이 아니었다..!! 이 문제는 유니온 파인드였다. 맨 처음 생각난 건 유니온 파인드였는데 문제 해석을 잘못했다. 결국 구해야하는 것은..
백준 3584번 가장 가까운 공통 조상 (C++) https://www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 우선 이 문제를 처음 접했을 때, 난 LCA알고리즘의 존재를 모르고 풀었다. 때문에 이 풀이가 100퍼센트 맞는 정답이라고는 말할 수 없다. 하지만 코딩테스트에서 모르는 알고리즘이 나와도 풀이할 수 있어야한다. LCA에 대해서는 다음 포스팅에 할 예정이다. 각 자식들은 단 하나의 부모를 가지고 있다. 먼저 A의 조상을 타고 올라간다. 그렇다면 루..
백준 1107번 리모컨 (C++) https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 내 접근 - Greedy 문제라고 생각했다. 만약 4987 인데 9가 금지라면 9대신에 가장 근접한 8을 배치하고 49XX보다 48XX가 더 작으므로 격차를 최소로 하기 위해 사용할 수 있는 가장 큰 값을 배치하여 4888로 지정하고 4987 - 4888 + 자리수 = 103 이렇게 생각했다. 그러나 이러면 자리수가 바뀔 때를 계산할 수 없다. 예를 들어 9998 이고 9가 금지..
백준 11000번 강의실 배정 (C++) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 이전에 풀었던 BOJ문제 공주님의 정원 문제와 비슷하다고 하여 풀어봤다. 공주님 문제를 어렵게 느꼈고 깨달은 것이 많은 문제여서 비장한(?) 마음으로 임했다. 먼저 최대한 수업시간들이 이어져있도록 꼬리물기를 시켜야한다. 그러므로 한 수업이 끝나고 다음 수업들의 수업을 스캔하는 과정이 필요하다. 1 2 1 2 2 7 2 4 3 7 이라고 가정하자. 그렇다면 먼저 1~2 수업을 할 것이다. 그리고 다음 수업시간의 시작 시간과 이전 수업 시간의 끝나..

티스토리툴바