Byeo

목차 개요 설명 코드 개요 어떤 tree가 주어졌을 때, 임의의 node에서 자신 혹은 자식 노드들 중에서 하나만 선택하면서 그 선택의 비용의 최솟값은 얼마인가를 구하는 문제입니다. 이 문제는 Tree DP인데, 특정 노드를 선택하는 Tree DP 특징 중에 하나로는 자신의 노드가 선택 되었는지, 안되었는지 구분해서 구하는 문제가 많습니다. 각각의 배열을 dpYes (dpYes[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택 되었을 때 그 비용) dpNo (dpNo[i]의 값은 i번째 node의 child를 모두 계산을 끝낸 뒤, 자신이 선택되지 않았을 때 그 비용) 로 구분하여 구하면 되겠습니다. 이 때, dpYes는 자식들을 순회하면서 min(dpYes[child], d..

목차 문제 풀이 코드 보기 문제 풀이 구간 합 구하기의 응용 버전입니다. Segment tree에 관한 설명은 다음 게시글을 참조하면 됩니다. 세그먼트 트리, BOJ2042 BOJ 2042에서는 각 노드에 구간 합을 저장했다면 이번에는 구간 곱을 저장하면 됩니다. ※ Check List! 매 계산할 때마다 1,000,000,007로 나눠야 합니다. 더하기와는 다르게 어떤 수 a와 b를 곱할 때 1,000,000,007 보다 작은 수를 곱하게 되겠죠. 그런데 이 값은 Integer를 초과합니다. 따라서 중간 과정은 모두 long type이어야 합니다. 빨간색으로 칠해진 node는 모두 1,000,000,007을 넘겨 modular 연산된 숫자들입니다. 만약, 저기서 modular연산을 해주지 않았다고 생각..