www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 정사각형을 만족하기 위해서 어떤 규칙이 필요할까? 행렬 i, j 를 기준으로 왼쪽, 위, 왼쪽 위가 모두 1인 것만이 정사각형이 된다. 이걸 확장시켜주면, 최종적인 점화식은 \(D[i][j] = min(d[i-1][j], d[i][j-1], d[i-1][j-1]) + 1\) 이 된다. 물론 조건문으로 현재 위치가 1이고 그 주변도 1임을 미리 따져줘야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ..

www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 배낭 문제의 변형이다. 메모리와 비용이 주어지는데 dp테이블을 메모리를 기준으로 채워야 하나? 생각했는데 비용을 기준으로 dp테이블을 채워줘야 한다. 예제를 보면 30 10 20 35 40 3 0 3 5 4 가 주어지는데 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 10 10 40 50 50 60 80 80 85 100 100 115 115 115 135 이런 식으로 테이블을 채워주고 그때..

www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 파일을 합칠 수 있는데 합치는데 드는 비용의 누적 합 중 최소가 되는 값이 정답이 된다. 재귀적으로 접근하면 그나마 쉽게 해 볼 수 있는데 그래도 어렵다.. 위 사진처럼 진행하는데 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다 연속이 되야 하기 때문에 따로 정렬이나 부분을 나누어서 접근하면 틀린다. d [i][j]..

www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net DP를 연습하던 중에 재미있는 풀이로 풀 수 있어서 가져와 봤다. k가 존재하면 (0, 0)에서 k가 존재하는 인덱스 (i, j)까지 의 길 찾기 경우의 수 \(nCk\)로 구하고 그 k에서 (n - 1, m - 1)까지의 경우의수를 또 구하면 된다. 나이브하게 풀면 오버플로가 나고 dp테이블에 조합을 저장해 두고 풀어야 한다. 1 2 3 4 5 6 7 8 9 10 11 1..

www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상 정렬 + DP 문제였다. 1번 노드에서 걸리는 작업을 모두 완료하고 2번과 3번 노드에서 작업을 시작할 수 있다. 2번 노드에서 걸리는 시간은 1초이지만, 3번 노드에서 걸리는 시간이 100 초기 때문에 4번 노드에서 작업을 시작하려면 1번 10초 + 3번 100초 가 걸리고 4번노드까지 마치면 120초가 정답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 ..

www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 시간이 0.5초, 메모리 제한이 무려 4MB 인 DP 문제다. 메모리 제한 때문에 탑-다운보다는 바텀-업 방식으로 해결했다. d [i]는 i를 만드는데 필요한 경우의 수로 놓고 풀어보면 d [j] += d [j- ar [i]] 가 식이 된다. d [j]를 만드는 경우의 수는 d [j- ar [i]] 를 어떻게든 잘 구해놓고 d [j - ar [i]] 를 더해준다. #include #include using nam..