tree dp (2) 썸네일형 리스트형 (C++) - 백준(BOJ) 17831 : 대기업 승범이네 https://www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net tree dp 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 사수, 부사수 관계를 인접 그래프로 나타내기 위한 변수 graph, 각 회사원의 능력을 입력할 일차원 배열 ability, 회사원의 수 n, dp함수를 수행하며 memoization을 수행할 d배열을 선언 후 입력받습니다. graph에 값을 저장할 때 i번 회사원의 사수를 입력하는 형태이므로 graph[사수.. (C++) - 백준(BOJ) 1949번 : 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net tree를 만들고 dfs를 수행하며 top down dp로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 마을마다 주민수를 입력받아 일차원 배열에 저장합니다. 2. 인접리스트로 무방향 그래프를 만들어 줍니다. 이를 graph라는 vector형 변수에 저장합니다. 3. 루트노드에서 출발하여 문제에서 나온 규칙을 계속해서 지켜가며 트리의 아래로 내려간다면 결국 답이 나온다는 줄기.. 이전 1 다음