사실 이 문제는 1주일 전에 푼거긴 한데 dynamic programming에서 bottom-up, top-down 기법의 차이를 분석하고 넘어가고자 포스팅하고자 한다. 13250번: 주사위 게임 효빈이는 1부터 6까지 수가 적혀있는 6면 주사위를 가지고 있다. 매번 주사위를 던질 때마다 주사위의 윗 면에 적힌 수 만큼 사탕을 받게 된다. 효빈이가 적어도 N개의 사탕을 받기 위해 주사위를 www.acmicpc.net 1. 문제 분석 dt[i] = i이상의 사탕을 가져올 때 주사위를 던진 횟수의 기댓값으로 지정했다. 또한 주사위는 1~6 자연수 이기에 해당 범위의 dt값에만 영향을 받는다. 2. Bottom-Up Bottom-Up은 문제를 작은 단위로 쪼갠 상태에서 부터 큰 단위로 범위를 확장해 나가는 방..

1521번: 랜덤 소트 첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열에 들어있는 수 N개가 주어진다. 이 수는 모두 1보다 크거나 같고, N보나 작거나 같으며, 같은 수는 2번 이상 주어지지 않는다. 또, N은 8보다 www.acmicpc.net 1. 문제 분석 N = 8이하 자연수라서 check배열을 이용해 최대 8!의 경우의 수를 구하여 답을 얻을 수 있다. 그리고 bfs와 memoization을 이용해 기댓값을 구하면 된다. 2. 실패 과정 살짝 확률을 경우의 수로 정의하는 것과 햇갈려서 횟수의 합과 경우의 수를 나눴다. 솔직히 이래도 괜찮지 않을까? 하고 무심코 넘어갔는데.. 1시간 고민 끝에 틀린 이유를 알 수 있었다. (아래 참고) 3. 성공 과정 위의 그림에서 쓴 글처럼 사실 어느 ..

최근에 이 문제를 풀고 큰 교훈을 얻어서 올려야지~ 하고 못했던 문제 중 하나입니다.. 복습할 문제들 보다가 이 문제가 눈에 띄어서 다시 올려봅니다. 27730번: 견우와 직녀 견우는 정점의 개수가 $N$인 무향 가중치 트리 $E$에 살고 있고, 직녀는 정점의 개수가 $M$인 무향 가중치 트리 $W$에 살고 있다. 두 사람은 각자 다른 트리에 살고 있으므로 만날 수 없다... 슬픔에 www.acmicpc.net 1. 문제 분석 A트리와 B트리가 존재할 때 A트리의 임의 노드 a, B트리의 임의 노드 b에 대하여 A의 모든 노드와 B의 모든 노드를 이동하는 비용의 합은 B.size * ( i -> a ) + A.size * (j -> b) + A.size * B.size 입니다. 그리고 i -> a 와 j..

16468번: 크리스마스 트리 꾸미기 이진트리란 각각의 노드가 최대 두개의 자식 노드를 가지는 트리 자료구조로, 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드가 있다. 제일 위에 노드가 1개, 그 다음 2개… 와 같은 식으로 위에 www.acmicpc.net 1. 문제 분석 및 풀이 이전 포스팅에서 트리 dp에 대해 다뤘는데 대부분의 아이디어가 해당 노드를 루트로 하는 부분 트리에 대한 dt를 설정하여 진행하는 방법이었다. 이 문제도 너무 뻔히 tree dp임을 보이고 그냥 쉽게 만들면 된다고 생각했지만 단 한 가지 간과한 사실이 있었다. dt[n][h] : 높이 h인 트리를 n개의 공을 이용해 만드는 가지 수 이렇게 정의하면 되는 것인가? 나는 처음에 된다고 생각했는데... 문제를 쫌 더 보니깐 트리..

2213번: 트리의 독립집합 첫째 줄에 트리의 정점의 수 n이 주어진다. n은 10,000이하인 양의 정수이다. 1부터 n사이의 정수가 트리의 정점이라고 가정한다. 둘째 줄에는 n개의 정수 w1, w2, ..., wn이 주어지는데, wi는 정점 i의 www.acmicpc.net 1. 분석 및 고찰 전에 포스팅했던 1272문제와 다른 tree dp문제를 경험했던 덕분에 각 노드가 루트가 되고 해당 노드의 상태가 0 혹은 1일때로 나누어 계산하면 된다는 점을 바로 깨달을 수 있었다. 2. 실패 이 문제는 추가적으로 back-tracking 과정을 걷혀야 하는데 이를 dp 업데이트 도중에 갱신하고자 하였으나 $N^2$의 공간 복잡도 문제로 고민하는 데 시간을 많이 소비하였다. 3. 성공 back-trackin..

1272번: 특별 노드 n(1 M; for(int i=1;i> w[i]; for(int i=1;i> x >> y; v[x].push_back(y); v[y].push_back(x); } for(auto&i:v[M]) ans += process(i, M, M); cout

출처 : https://www.acmicpc.net/problem/28220 28220번: 블록 쌓기 첫 번째 줄에 $N$, $L$, $R$이 공백으로 구분되어 주어진다. 두 번째 줄에 $A_1$, $\dots$, $A_N$이 공백으로 구분되어 주어진다. www.acmicpc.net 1. 문제 설명 1~N번 칸이 존재하며 i번 칸에 {A_i}개의 블록이 쌓여있다. 각 칸에 쌓인 블록의 개수가 L이상 R이하가 되면서 {A_i}를 오름차순이 되도록 배치하고자 한다. 블록은 한 번에 양 옆으로 한 개씩만 옮길 수 있다. 블록을 옮기는 횟수의 최솟값을 구하라. 2. 실패 1 1) 접근 과정 이 문제를 처음 봤을 때 해당 조건을 만족하되 {A_i}가 최소이면 될 것이라고 간과하였다. 그래서 그리디로 접근해 보았다..