동적 계획법13 [BOJ] 백준 1149번: RGB거리 www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 동적 계획법을 사용하는 문제입니다. i번째 집을 j번째 색으로 칠할 때의 비용 color[i][j]에 대하여 i번째 집까지 색을 칠할때 i번째 집을 j번째 색으로 칠하는 최소비용을 dp[i][j]라고 한다면 이웃한 집은 같은색으로 칠하면 안되므로 dp[i][j] = min(dp[i][j], dp[i-1][k] + color[i][j]) 단, k ≠ j 이 됩니다. #include #incl.. 2020. 10. 21. [BOJ] 백준 1697번: 숨바꼭질 www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 순간이동이 현재 좌표에 2배까지 가능하므로 최대 배열 크기를 20만으로 잡고, dp[i]는 i 좌표로 이동하는데 걸리는 최소 시간이라고 보면 아래 코드와 같이 해결 가능합니다. 먼저 n보다 작은 좌표 위치는 -1 로 이동할 수밖에 없으므로 최소 시간은 n - i로 초기화해주고 과정 1. 반복적으로 +1 이동하는 경우 과정 2. 2배 이동하는 경우 두 가지 경우에 대하여 최솟값을 .. 2020. 9. 7. [BOJ] 백준 1028번: 다이아몬드 광산 https://www.acmicpc.net/problem/1028 1028번: 다이아몬드 광산 첫째 줄에 R과 C가 주어진다. R과 C는 750보다 작거나 같은 자연수이다. 둘째 줄부터 R개의 줄에는 다이아몬드 광산의 모양이 주어진다. www.acmicpc.net R, C 가 750으로 (i, j) 좌표에서 우측 하단으로의 대각선 길이 DP[i][j][0], 좌측 하단으로의 대각선 길이 DP[i][j][1], 좌측 상단으로의 각선 길이 DP[i][j][2], 우측 상단으로의 대각선길이를 구해놓고 모든 좌표에 대하여 O(R*C*750*4)의 복잡도로 가능한 다이아몬드 크기를 구할 수 있습니다. (시간초과가 날것 같지만 가지치기를 통해 충분히 시간을 줄일 수 있습니다.) #include #include #i.. 2020. 8. 12. [BOJ] 백준 11049번: 행렬 곱셈 순서 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같� www.acmicpc.net 행렬 곱셈 순서에 따라 연산량이 적어지는데 잘 생각해보면 (a b) (b c) 차원인 두 행렬을 곱할 때 a * b * c 의 연산횟수가 필요하다. 즉 가운데 b가 큰 순서대로 먼저 곱하는것이 횟수를 줄일 수 있다. 하지만 당장 b가 큰것을 줄이는 순서가 최종적으로 최적의 방법이 아닐 수 있기 때문에 구간 s~e 에서 모든 연산을 수행해봐야 한다. DP[s][e]를 s 번째 행렬과 .. 2020. 8. 6. 이전 1 2 3 4 다음
