공부공간

3중 for 문을 활용하여 풀어야 하는 동적 프로그래밍 문제이다. 파일은 연속되는 것들만 합치기가 가능하며, 파일을 계속 합치며 도출 되는 비용이 최소가 되도록 알고리즘을 구성해야 한다. 알고리즘 풀이에 쓰이는 배열 1. dp[i][j] 배열은 i 부터 j 장까지 최소 비용이라고 정의하고, 첫 번째 장부터 마지막 장까지 최소 비용의 값을 갱신하며 값을 도출한다. 이러한 정의로 다음과 같은 점화식을 도출할 수 있다. 2. cost[i] 배열은 주어진 파일을 합치는 비용을 저장하는 배열이다. 3. sum[i] 배열은 i 까지의 파일을 합하는데 필요한 비용을 나타낸다. 예를 들어, 첫 번째 경우 예제 입력에서 주어진 값을 사용한다면, sum[2] = 70 이고 sum[i] = sum[i-1] + cost[i]..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 www.acmicpc.net 주어진 N x M배열에서 일부를 90도 회전시켜서 행의 합의 최솟값을 구하는 문제이다. 행의 합이 최소가되기위해서 DFS로 일..