본문 바로가기
728x90

다이나믹프로그래밍30

[python] 백준 1670 정상 회담2 https://www.acmicpc.net/problem/1670 1670번: 정상 회담 2 첫째 줄에 정상 회담에 참가한 사람의 수 N이 주어진다. 이 값은 10,000보다 작거나 같은 짝수이다. www.acmicpc.net 문제 해결 원 안에서 짝을 짓는 것을 할 때는 보통 한 사람을 기준으로 하게 된다. 그 한사람이 짝을 이뤘을 때를 생각한다. (짝은 무조건 이루어진다.) 그러면 반이 나눠지는데 양쪽 모두 국가가 짝수개가 있어야한다. 그 개수가 j개 ,(n-2-j)개라고 하자. 그리고 (j 2023. 5. 9.
[python] 백준 1328 고층 빌딩 https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 문제 해결 dp를 써야겠다라는 생각이 드는데 어떻게 써야할지 고민이 되는 문제 n이 1이상 100이하이기 때문에 삼 중 반복문을 써도 괜찮다. dp[i][j][k]를 i개의 빌딩이 있을 때 왼쪽에서 보면 j개 오른쪽에서는 k개 보이는 배열가지수라고 하자. 그러면 dp[1][1][1] =1 이 된다. 가장 기본 값 i-1개의 빌딩이 배열되어있다고 하자. 이제 빌딩 하나를 더 세워 dp[i][j][k.. 2023. 5. 8.
[python] 백준 1949 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 10,000) 둘째 줄에는 마을 주민 수를 나타내는 N개의 자연수가 빈칸을 사이에 두고 주어진다. 1번 마을부터 N번 마을까지 순서대로 주어지며, 주민 수는 10,00 www.acmicpc.net 문제 해결 이웃한 마을, 즉 연결되어있는 지역으로 가면 안된다는 것이 어려운 부분이다. 이를 dp[i][0], dp[i][1] 로 두가지로 나눠서 i번째 마을을 포함하지 않은 누적 최대합과 i번째 마을을 포함하는 누적 최대합으로 나눠서 계산을 한다. 그럼 어떻게 모든 마을의 경우의 수를 계산하는가? dfs(깊이 우선 그래프)를 이용해 모든 마을을 순찰하면서 최대 합을 구할 수.. 2023. 5. 7.
[python] 백준 2157 여행 https://www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 문제 해결 처음에 다익스트라로 풀려고 했으나 k가 매우 클 수 있는 바람에 시간초과가 났다. 큰 수를 계산해야할 때는 무조건 dp가 된다! 그럼 dp를 어떻게 잡아야할까? 우선 똑같은 출발지에서 도착지점까지 항공로가 여러가지가 있을 수 있기 때문에 graph를 $ n \times n$ 행렬을 만든다음 graph[i][j]의 값읠 i에서.. 2023. 5. 7.
728x90