dp

[C++] 백준 1005번 탈출

1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 그래프 탐색과 DP를 통해 해결할 수 있는 문제. 특정 건물을 짓기 위해 어떻게 빨리 지을 수 있는 지 알아내는 알고리즘을 작성하는 문제였다. 알고리즘 분류를 보니, 위상 정렬이라는 알고리즘이 있었는데 해당 알고리즘에 대해서는 내가 아는 바가 없었지만 풀 수는 있었다. 문제 풀이 예시 이미지를 통해 문제를 해석해 보았다. 4번 건물을 짓기 위해서는 10초의 시간이 필요하며, 2번과 3번의 건물이 지어져 있어야 한다. 2번 건물을 짓기 위해서는 1초의 시간이..

[C++] 백준 1932번 정수 삼각형

다이나믹 프로그래밍 문제. 경우의 수를 나눠서 Bottom Up 방식으로 문제를 해결하면 된다. 처음에 그림을 보고 트리 -> 그래프 탐색인 줄 알았는데 문제를 읽어보고 그림을 그려보니까 다이나믹 프로그래밍이란 것을 알았다. 그림을 보면 각 노드에서 아래로 내려오면서 그 노드의 최대값을 갱신해 나가면 된다. 이 때 방향을 보면 맨 첫번째 노드는 각 전단계의 첫번째 노드에서만 온다는 것을 알 수 있다. 그리고 마지막 노드는 전단계의 마지막 번째의 노드에서만 온다는 것을 알 수 있다. 첫번째, 마지막 둘 다 아니라면 전 단계의 왼쪽, 오른쪽 노드에서 온다는 것을 알 수 있다. 점화식을 세우면 다음 그림과 같다. dp[i][j]는 i, j의 최대값을 저장하는 배열이고 triangle[i][j]는 i, j의 가..