목록백준/Dynamic Programming (32)
mojo's Blog
문제 링크 => 10942번: 팰린드롬? (acmicpc.net) 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 문제가 약간 이상한 느낌인게 칠판에 적는 숫자가 항상 1의 자리 숫자인 것 같다. 예를 들어서 1, 23, 232, 1, 232, 32, 1 에 대한 palindrome 처리를 할 때 [2, 3] 에 대한 Query 는 true 가 나와야 함에도 불구하고 통과한 코드는 false 처리를 한다는 것이다. 그래서 모든 input 을 1의 자리로 생각하고 풀었더니 굉장히 간단해졌다. Optimal Substruc..
문제 링크 => 1958번: LCS 3 (acmicpc.net) 1958번: LCS 3 첫 줄에는 첫 번째 문자열이, 둘째 줄에는 두 번째 문자열이, 셋째 줄에는 세 번째 문자열이 주어진다. 각 문자열은 알파벳 소문자로 이루어져 있고, 길이는 100보다 작거나 같다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 알고리즘 수업때 배웠던 LCS 에서 문자열이 하나 더 추가되어 총 3개의 문자열의 LCS를 구해야 한다. 문자열 X, Y, Z 가 있다고 할 때 Optimal Substructure은 다음과 같다. 이때 LCS(X, Y, Z) 를 X, Y, Z 문자열들의 Longest Common Subsequence 값이라고 할 때, Xn == Yn == Zn 일 경우 => LCS(Xn, Yn, ..
문제 링크 => 11066번: 파일 합치기 (acmicpc.net) 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 이 문제는 알고리즘 시간때 배웠던 행렬 곱 연산을 최소로 만드는 그 문제와 비슷해서 한번에 풀렸다. T(i, j) = 파일 i 번째에서 j 번째까지를 하나의 파일로 합칠 때 최소 시간 S(i, j) = 파일 i 번째에서 j 번째까지를 합치는 과정에서 걸리는 최소 시간 예를 들어서 20, 50, 30 이 있다고 하자. S(1, 1) = 20, S(2, 2) =..
문제 링크 => 1915번: 가장 큰 정사각형 (acmicpc.net) 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 다이나믹 프로그래밍 문제이다. 위와 같이 (i - 1, j - 1) 일때의 최대 넓이와 현재 (i, j) 로부터 왼쪽으로의 1의 최대 갯수와 윗쪽으로의 1의 최대 갯수를 활용하여 현재 (i, j) 의 원소가 0, 1인지를 구분하여서 접근하면 된다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #define INF 100000000 using namespace s..
문제 링크 => 2565번: 전깃줄 (acmicpc.net) 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 다이나믹 프로그래밍 문제이다. 최대 전깃줄이 되도록 하려면 B전봇대로 연결된 전깃줄 중에 오름차순으로 연결될 수 있는 경우 중에 최댓값을 구해줘야 한다. Solution Code #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int dp[501]; bool compare(pair x, pair y) { return..
문제 링크 => 11051번: 이항 계수 2 (acmicpc.net) 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 다이나믹 프로그래밍 문제이다. C(N, K) 를 이항계수 N(N-1)...(N-K+1) / 1*2*...*K 라고 할 때 Optimal substructure는 다음과 같다. K = 0 => C(N, K) = 1 K != 0 => C(N, K) = C(N, K-1) * (N - K + 1) / K % 10007 이 때 나누기 연산이 좀 거슬려 보인다. 여기서 10007은 prime 임을 이용하여 fermat's theorem 을 이용해 보도록 하자. x^(m-1) ..