LIS 알고리즘 (1)

LIS는 제목에서도 명시해놨듯이 수열중 증가하는 가장 긴 부분수열을 찾는 문제이다.

{1, 6, 2, 5, 7, 3 ,5}라는 수열의 Increasing Subsequece는 {1, 2}, {2, 5, 7}, {1, 2, 3, 5}... 등이 될 수 있다. 이 중에서 가장 긴 수열을 찾는 문제이다.

증가하는 수열을 찾기위해서는 앞에서부터 탐색후 값을 저장하여 누적시키는 방식으로 한다.

각각의 최장수열길이를 DP[n]에 저장한다.

#include <cstdio> #define max(a,b) ((a>b)?a:b) int main(){     int N;     int arr[1001];     int DP[1001] = { 1 };     int ans = 1;     scanf("%d", &N);     for (int n = 0; n < N; n++)         scanf("%d", &arr[n]);     for (int i = 1; i <= N; i++){         DP[i] = 1;         for (int j = 0; j < i; j++){             if (arr[i] > arr[j] && DP[i] < DP[j] + 1){                 DP[i] = DP[j] + 1;                 ans = max(ans, DP[i]);             }         }     }      printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs

백준 11055 가장 큰 증가하는 부분 수열 https://www.acmicpc.net/problem/11055

       1965  상자 넣기                        https://www.acmicpc.net/problem/1965

       11053 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053

       1937  욕심쟁에 판다                   https://www.acmicpc.net/problem/1937
       2352  반도체 설계                      https://www.acmicpc.net/problem/2352
       11722 가장 긴 감소하는 부분 수열 https://www.acmicpc.net/problem/11722
       2643 색종이 올려놓기                 https://www.acmicpc.net/problem/2643
       11568 민준이의 계략                 https://www.acmicpc.net/problem/11568

1699 제곱수의 합

백준 1699 제곱수의 합 https://www.acmicpc.net/problem/1699

어떤수 N (10만 이하의 자연수)에 대하여 제곱수가 되는 최소 항을 찾는 문제이다.

D[N]을 N의 제곱수의 합의 최소 항개수 라고 정의하였을 때
자연수중에 한 수의 제곱으로만 이루어진 제곱수에 D[N]을 계산하는 방식으로 문제를 해결하였다.

예를들어 4라는 숫자는 2의제곱으로 하나의 항을 가지는 제곱수이다.
이다음에 오는 5는 당연히 제곱수가 아니기 때문에 4+1로 2개의 항을 가진다.
그다음 수 6도 4+1+1로 구성되겠다.

이렇게 N을 1부터 N까지 증가시키며 D[N]을 채워나간다.
물론 계속 제곱수를 발견한다음 1씩 더해가면 안된다.

12라는 숫자를 보면 가장 가까운 제곱수인 9에 3을 더하는 경우로
9+1+1+1 : 4개의 항이 나온다. 하지만 4+4+4로 더 작은 3개의 항이 존재한다.

그러므로 D[N]에 지금까지 구했던 D[N]을 더해 더 작은 항에 대한 경우도 고려를 한다.

D[N+M] = min(D[N+M], D[N] + D[M])

#include <cstdio> #include <cmath> #define min(a,b) ((a<b)?a:b) bool soonsu(int num){     int x = (int)sqrt((double)num);     if (x*x == num)         return true;     return false; } int main(){     int N;     int D[100001] = { 0 };     scanf("%d", &N);     for (int n = 1; n <= N; n++){         if (soonsu(n)){            //순수 제곱수             D[n] = 1;             for (int m = 1; n + m <= N; m++){                 if (D[n + m] > 0)                     D[n + m] = min(D[n + m], D[n] + D[m]);                 else                     D[n + m] = D[n] + D[m];             }         }     }     printf("%d\n",D[N]);     return 0; } d Colored by Color Scripter

cs

더 깔끔한 점화식을 사용한 사람이 많았지만 이것도 방법이니까...

2156 포도주 시식

백준 2156 포도주 시식 https://www.acmicpc.net/problem/2156

다음과 같은 규칙이 적용된다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

2579 계단오르기와 유사해 보이는 문제이지만 포도주 잔을 선택할때에 대한 조건은 없다.

즉, 시작점과 끝점 모두 불분명하다는 것이다.

연속적으로 3잔을 모두 마실 수 없는것을 이용해서 

현재를 기준으로 0잔 마셨을 때 , 1잔 마셨을 때, 2잔 마셨을 때로 점화식을 세워보면

DP[N][M] : N까지 현재 M잔 마셨을 때 마신 최대 포도주 양

1. M = 0

현재 0잔 마셨으므로 N-1기준으로 0잔,1잔,2잔 마신 최댓값을 구하면 된다.

DP[N][0] = max(DP[N-1][0], DP[N-1][1], DP[N-1][2])

2. M = 1

현재 1잔 마셨으므로 N-1기준으로는 0잔 마신 경우밖에 없다.

 DP[N][1] = DP[N-1][0] + Wine[N]

3. M = 2
현재 2잔 마셨으므로 N-1기준으로는 1잔 마신 경우밖에 없다.

DP[N][2] = DP[N-1][1] + Wine[N]

#include <cstdio> #include <algorithm> using namespace std; int main(){     int N, arr[10001] = { 0 };     int D[10001][3] = { 0 };     scanf("%d", &N);     for (int n = 0; n < N; n++)         scanf("%d", &arr[n]);     D[1][2] = D[1][1] = arr[0];     for (int n = 2; n <= N; n++){         D[n][0] = max(max(D[n - 1][0], D[n - 1][1]), D[n - 1][2]);         D[n][1] = D[n - 1][0] + arr[n - 1];         D[n][2] = D[n - 1][1] + arr[n - 1];     }     printf("%d\n", max(max(D[N][0], D[N][1]), D[N][2]));     return 0; } Colored by Color Scripter

cs