다이나믹 프로그래밍 문제 2
1. 가장 긴 증가하는 부분 수열(LIS) 문제 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. www.acmicpc.net 풀이 #include #include #include using namespace std; int main() { int n, max = 1; cin >> n; vector d(n + 1, 1); vector a(n + 1, 0); for (int ..
다이나믹 프로그래밍 문제
1. 1,2,3 더하기 5 문제 : https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 #include #include #include using namespace std; int main() { int m; cin >> m; int l = 100000; long long mod = 1000000009; vector d; d.assign(l+1, vector(4)); // 초기화 d[1][1] = 1, d[1][2] = 0, d[1][3] = 0; d[2][1] = 0, d[2][2] = 1,..
