1106 호텔 (G4) dp[i] = 고객 i명을 유치하기 위해 필요한 최소 비용 http://boj.kr/eda56c043fe04b94863a76278da6f9a4 2624 동전 바꿔주기 (G4) dp[i] = i원을 만들 수 있는 방법의 수 http://boj.kr/0c30a754956b47ba8af519f7861feffb 12869 뮤탈리스크 (G4) dp[a][b][c] = SCV 3개의 체력이 각각 a,b,c일 때, SCV들을 모두 파괴하는 데 필요한 최소 공격 횟수 SCV의 체력이 최대 60이므로 상태 공간을 60*60*60으로 설정한다. BFS를 돌리면서 최소 공격 횟수를 dp 테이블에 기록한다. 최종 정답은 모든 SCV가 파괴된 상태인 dp[0][0][0]이다. http://boj.kr..
8913 문자열 뽑기 (G3) 문자열의 길이가 최대 25이므로 모든 경우에 대해서 재귀적으로 각 그룹들을 제거하면서 빈 문자열이 되는지 확인하면 된다. http://boj.kr/d0f8be3020c64594a794f24b69baf0d6 11062 카드 게임 (G3) dp[i][j] = i에서 j까지의 카드들이 남아 있을 때, 근우가 가져갈 수 있는 최대 점수 근우가 카드를 가져갈 때, 가장 왼쪽 카드 또는 가장 오른쪽 카드를 가져갈 수 있다. 이 때 명우가 최적의 선택을 했을 경우 남아있는 카드들 중에서 명우가 얻는 점수를 뺀 값을 근우의 점수로 기록한다. http://boj.kr/9d3a5872aab64fe6b3ac294b7ac8d865 14428 수열과 쿼리 16 (G1) 세그먼트 트리로 구간의 ..
1949 우수 마을 (G2) dp[node][0] = 해당 노드를 선택하지 않았을 때, 자식 노드에서 얻을 수 있는 최대 주민 수dp[node][1] = 해당 노드를 선택했을 때, 자식 노드에서 얻을 수 있는 최대 주민수 위와 같이 정의하고 DFS를 이용해서 트리에서의 DP 테이블을 계산해준다. 최종 정답은 루트 노드에서 선택한 경우와 선택하지 않은 경우 중 최댓값이다. http://boj.kr/ff3f639352ba41309973b3102f4e1ff1 14267 회사 문화 1 (G4) 상사에서 부하로 이어지는 단방향 트리를 만든다. 이후 칭찬에 대한 정보가 주어질때마다 매번 DFS를 돌리는것이 아니라 칭찬의 시작점에만 기록을 해놓는다. 그리고 루트에서부터 DFS를 한번만 돌리면서 칭찬을 누적해서 더해..