DP

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에www.acmicpc.net풀이과정처음에는 단순하게 DFS 재귀 백트래킹을 이용하여 구현했다.하지만, DP를 사용하지 않으면 시간초과가 났다. 괜히 골드3 문제가 아니다.DP와 DFS를 같이 사용해야 하는 새로운 문제 유형이었다.만약 이 그림 (0, 0)에 판다를 냅둔다면, (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (1, 1) 을 통해서 총 5일을 살게 될 것이다. 그럼 dp[0][0] ..

https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 풀이과정 dp와 위상정렬을 같이 쓰는 문제다. 위상정렬 함수를 보면 진입차수가 0일 경우(1,4,6번 노드)에 큐에 푸시를 하며 정답 배열에 1을 넣어준다. 그리고 큐가 비어있지 않을 때까지 연결되어있는 노드를 돌며 dp를 해주며 최종적으로 max인 값(res)를 출력해준다. #include #include #include #include using namespace std; int N, M, A, B; int indegr..

https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 풀이과정 dp와 위상 정렬을 같이 쓰는 문제이며 1005 ACM Craft 문제와 비슷한 문제이다. 이처럼 위상정렬과 dp가 같이 쓰이는 문제가 많은 것 같다. 풀이 과정은 1005번 문제와 같지만, 처음에 입력문에서 v를 푸시하는 과정에서 반대로 푸시를 해 고생을 먹었던 문제이다. 몇 번 노드에 몇 번 노드를 푸시해줄 것인지 방향을 잘 생각해서 입력받아야 한다. 도착점이 정해져있지 않으..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이과정 이 문제는 dp와 위상 정렬을 같이 쓰는 문제이다. res배열이 dp이고, 각 지점을 지날 때 가장 오래 걸리는 시간을 넣는 배열이다. #include #include #include #include using namespace std; int T, N, K, x, y, W; int build[1001]; int indegree[1001]; // 진입차수 int res[1001]; ..