이모저모

트리를 활용하는 dp 문제로 dp + dfs를 합쳐서 구현하면 된다. 점화식은for all childdp[parent][0] += max(dp[child][0], dp[child][1])dp[parent][1] += dp[child][0]최댓값은 0,1중에 선택하면 된다. 방문 정점을 찾고자 할 때는점화식을 구한 방식을 이용하여 최댓값을 선택한 루트부터 차례대로 tracking 을 하면 찾을 수 있다. 아래는 문제의 해결방법 소스코드이다. #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1..

시도1. dp[p][np][npp] : 현재 위치가 p일때 p+1 가 np만큼 움직였고, p+2가 npp만큼 움직인 상황에서 최소 횟수 p 위치에서 위 또는 아래로 1,2,3개를 같이 움직여서 p위치에 원하는 값을 맞추고 다음 p+1로 움직인다. 하지만 p 위치에서 1개를, 2개를, 3개를 조합해서 돌릴 경우가 존재할 수 있으며 위에는 그 경우의 수를 포함하지 않는다.해결방법dp[p][m1][m2][m3] : 위치가 p일때 p,p+1,p+2 위치에 대해 움직임이 m1,m2,m3 일때 최소 이동 횟수 위의 문제를 해결하기 위해 조합을 통해서 문제를 풀수 있게 바로 p+1로 움직이는게 아니라 1~9까지 움직여 보는 것이다. dp를 적용할 때는 모든 경우의 수를 포함할 수 있는지 꼭 점검해야 겠다.!!(물론 ..

BOJ 문제 https://www.acmicpc.net/problem/10272 해결방법시작점에서 끝점까지 순방향으로 가고 역방향으로 끝점에서 시작점으로 가야하기 때문에 다음과 같은 점화식이 성립한다.dp[p][bp] : 순방향의 위치가 p, 역뱡향의 위치가 bp 일때 이후 거리의 최솟값dp[p][bp] : min(dp[next][bp] + dist(p,next), dp[p][next] + dist(bp, next)) #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define MOD 1000000007#de..