펭로그

문제링크 : https://noj.am/8916 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071// BOJ 8916 이진 검색 트리#include using namespace std; long long comb(int n, int r) { // nCr r = n - r > r ? r : n - r; long long result = 1; for (int i = 0; i tc; while (tc--) { int num, input; vector tree(1); cin >> num; while(num--) { int i..

문제링크 : https://boj.kr/2805 1. 동적계획법(DP)을 이용한 풀이법 : 시간복잡도 O(N)나무의 길이가 제일 큰 것부터 시작하여 한단계씩 내려오면서 누적 합이 입력에서 주어진 값보다 클 때까지 구하는 방법으로 풀었다.입력 받은 값들을 내림차순으로 정렬하고 맨 첫번째 인덱스에 해당하는 값부터 시작하여 1씩 높이를 빼가면서 계산했다. 나무의 높이(arr[N])가 기준 높이(result)보다 높은 부분 까지만 인덱스를 탐색하고 기준 높이 이하(arr[N] - result)가 0 이하인 값들)가 나오면 현재 누적 잘린 나무들의 합이 정답보다 작다면 계속 루프를 진행한다.이때, 높이를 1씩 빼게되면 현재까지 진행해왔던 나무들의 높이가 각각 1씩 추가되기 때문에 sum += ptr 구문을 넣어 ..