문제 링크 http://icpc.me/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 비트마스크 dp문제다. dp[자릿수][마지막 수][사용한 수]로 정의하면 dp[i][j][k | (1

풀이 dp[현재 사람][이전까지 수행한 일의 상태] = 현재 일의 상태까지의 최솟값 이 문제는 비트마스크와 dp를 이용하여 풀이할 수 있다. 이전까지 수행한 일의 상태를 0011 -> 1, 2번이 일을 한 상태와 같이 비트를 이용하여 상태를 표시한다. 코드 #include #include int d[22][22]; int dp[22][1 b ? b : a; } int dpf(int cur, int state) { int &ret = dp[cur][state]; //모든 일을 한 상황 ex) n = 3일때 1000 - 1 = 0111 if (state == (1

풀이 방법 이 문제는 트리 + dp를 이용하는 문제이다. dp는 dp[현재 노드 번호][현재 노드가 우수인지 아닌지 여부]로 정의한다. 2번 조건에 의해 현재 노드가 우수 마을이면 항상 다음 노드는 우수 마을이 아니고, 우수마을이 아니라면 다음 노드는 우수마을일수도 있고 아닐 수도 있다. 3번 조건은 1번 조건에 의해 자연스럽게 만족된다. 우수x -> 우수x -> 우수x 이런식으로 계속해서 될 수 있다고 착각을 하여 시간을 많이 뺏겼다. 하지만 우수x -> 우수x -> 우수x 이 상황은 항상 올 수 없다. 왜냐하면 우수x -> 우수x -> 우수x 이 상황보다 우수x -> 우수 -> 우수x 이 상황이 항상 더 크기 때문에 최댓값을 유지하기 위해서는 우수x가 계속해서 올 수 없다. 코드 #include #i..

풀이 방법 이 문제는 트리에서 dp를 이용하는 문제이다. dp[현재 노드][현재 노드가 얼리어답터인가 여부]로 dp테이블을 만들고 현재 노드가 얼리어답터가 아니라면 자식노드는 항상 얼리어답터이고, 얼리어답터라면 얼리어답터일수도, 아닐수도 있다. 이 문제는 이 문제 와 매우 비슷하여 쉽게 해결하였다. 코드 #include using namespace std; vector v, tree; int dp[1000006][2]; bool visited[1000006]; //단방향 그래프로 바꾼다 void dfs(int cur) { if (visited[cur]) return; visited[cur] = true; for (auto nxt : v[cur]) { if (!visited[nxt]) { tree[cur]..