IT세상

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net for문을 반대로 쓰는게 살짝 헷갈렸는데 가장 긴 증가하는 부분수열이랑 똑같이 풀어주면 된다 #include using namespace std; int n; int dp[1001] = {0}, a[1001] ={0}; int main(void) { cin >> n; for(int i=1; i> a[i]; dp[i] = 1..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net #include using namespace std; int n; int dp[10001] = {0}, arr[10001]={0}; int main(void) { cin >> n; for(int i=1; i> arr[i]; dp[1] = arr[1]; dp[2] = arr[1] + arr[2]; for(int i=3; i

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #include using namespace std; int n; int dp[101][10]={}; #define mod 1000000000; int main(void) { cin >> n; dp[1][0] = 0; for(int i=1; i

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net #include using namespace std; int tc, n; int dp[11]={0,1,2,4}; int main(void) { cin >> tc; for(int i=4; i n; cout

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 위 그림처럼 점화식은 dp(n) = dp(n-1) + 2 X dp(n-2)가 된다 #include using namespace std; int n; int dp[1001]; int main(void) { cin >> n; dp[1] = 1; dp[2] = 3; for(int i=3; i

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 2 x n 크기의 타일을 채우는 문제이고 DP를 이용한다. 그래서 점화식은 dp(n) = dp(n-1) + dp(n-2) #include using namespace std; int n; int arr[1000]; int main(void) { cin >> n; arr[0] = 1; arr[1] =2; for(int i=2; i

최장 증가 부분 수열 알고리즘(Longest Increasing Subsequence, LIS) #include using namespace std; int n; vector arr; int main(void) { cin >> n; for(int i=0; i> x; arr.push_back(x); } // 순서를 뒤집어 '최장 증가 부분 수열' 문제로 변환 reverse(arr.begin(), arr.end()); // DP 테이블 초기화 : arr[i]를 마지막 원소로 가지는 부분수열의 최대 길이 int dp[2000]; for(int i=0; i

#include using namespace std; int testCase, n, m; int arr[20][20]; int dp[20][20]; int main(void) { //테스트케이스 입력 cin >> testCase; for(int tc = 0; tc> n >> m; for(int i=0; i arr[i][j]; } } // 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화 for(int i=0; i

#include using namespace std; int n, m; vector arr; int main(void) { cin >> n >> m; // n개의 화폐 단위정보 입력받기 for(int i=0; i> x; arr.push_back(x); } vector d(m+1, 10001); //DP테이블 초기화 d[0] = 0; for(int i=0; i

#include using namespace std; int n; int d[30001]; //DP 테이블 초기화 int main() { cin >> n; d[0] = 0; d[1] = 1; //다이나믹 프로그래밍 진행(보텀업) for(int i=2; i