공부흔적

문제 링크

풀이 )

  M이 1,000,000 이하이므로 cin으로 입력을 받을 시 cin.tie(null), ios::sync_with_stdio(false) 처리를 해주어야 한다.

  또 각 경우에 대해서 O(n^2)인 경우 시간 초과가 발생하게 되므로 해결하기 위해 DP를 이용했다.

  먼저 dp 배열의 행과 열은 각각 시작, 끝을 의미한다.

  dp 배열의 모든 원소 값을 -1로 초기화 시킨다.

  check( )는 시작 s와 끝 e에 대해서

• dp[s][e]가 갱신된 적이 있다면(dp[s][e] != -1), 즉 팰린드롬 여부가 결정된 경우 바로 결과를 반환한다.
• e == s인 경우 즉 글자 하나인 경우 팰린드롬이므로 dp[s][e]를 갱신하고 true 반환
• e < s 인 경우가 오는 경우는 피호출함수에서 매개변수간 차가 1인 경우 예를 들어 check(1, 2)와 같은 경우 뿐이다.
  함수가 호출되기 위해서는 arr[1]와 arr[2]가 같아야 하기 때문에 길이가 2이고, 두 문자가 같다는 의미이다
  따라서 dp[s][e]를 갱신하고 true 반환
• 양쪽 끝 문자가 다른 경우 팰린드롬이 아니므로 dp[s][e]를 갱신하고 false 반환
• 양쪽 끝 문자가 같은 경우 양쪽에서 한칸씩 당기면서 팰린드롬인지 여부 확인

#include <iostream>

using namespace std;

int arr[2000];
int dp[2000][2000];

bool check(int s, int e){
    if(dp[s][e] != -1)
        return dp[s][e];

    if(e <= s)
        return dp[s][e] = true;

    if(arr[s] != arr[e])
        return dp[s][e] = false;

    return dp[s][e] = check(s+1, e-1);
}

int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m;

    for(int i = 0; i < 2000; ++i)
        for(int j = 0; j < 2000; ++j)
            dp[i][j] = -1;

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> arr[i];

    cin >> m;
    while(m--){
        int s, e;
        cin >> s >> e;
        cout << check(s-1, e-1) << '\n';
    }
    return 0;
}

문제 링크

풀이 ) DP

  문자열로 입력을 받은 후 다음 case로 나눈다.

• 0인 경우(00) : 불가능
• 한자리 수인 경우(01~09) : 뒤의 한자리를 제외한 n-1자리로 만든 경우의 수
• 26이하인 경우 중 10의 배수인 경우 : 뒤의 두 자리를 제외한 n-2자리로 만든 경우의 수
• 26이하인 경우 중 10의 배수가 아닌 경우 : 뒤의 한자리와 두 자리를 제외한 n-1, n-2자리로 만든 경우의 수의 합
• 27이상인 경우 중 10의 배수인 경우 : 27이상의 숫자로도 만들 수 없고 끝이 0이므로 불가능
• 27이상인 경우 중 10의 배수가 아닌 경우 : 뒤의 한자리를 제외한 n-1자리로 만든 경우의 수

#include <cstdio>
#include <string.h>

int memo[5001] = {1, 1};

int main(void)
{
    char p[5001] = "";
    scanf("%s", p);

    if(p[0] == '0'){
      printf("0\n");
      return 0;
    }
    for(int i = 2; i <= strlen(p); i++){
        int num = (p[i-2]-'0')*10 + p[i-1]-'0';
        if(num == 0){
            printf("0\n");
            return 0;
        }
        else if(num < 10){
            memo[i] = memo[i-1];
        }
        else if(num < 27){
            if(p[i-1] == '0'){
                memo[i] = memo[i-2];
                continue;
            }
            memo[i] = memo[i-1]+memo[i-2];
        }
        else{
            if(num%10 == 0){
                printf("0\n");
                return 0;
            }
            memo[i] = memo[i-1];
        }
        memo[i] %= 1000000;
    }
    printf("%d\n", memo[strlen(p)]);
    return 0;
}

주의점 )

  - memo 배열을 초기화할 때 처음 두 원소를 1, 1로 초기화해주어 두 자리 이상에 대하여 memo[i-1]과 memo[i-2]를 모두 구할 수 있도록 해주어야 한다.

  - 0이 입력되는 경우를 위해 예외처리를 해준다.

문제 링크

풀이 ) DP - LIS

  문제를 읽어보면 LIS 유형임을 쉽게 파악할 수 있다.

#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
  int n, box[1001], memo[1001], ans = 0;
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", box+i);

  fill(memo, memo+sizeof(memo)/sizeof(int), 1);
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < i; ++j)
      if(box[i] > box[j])
        memo[i] = max(memo[i], memo[j]+1);
    ans = max(ans, memo[i]);
  }
  printf("%d\n", ans);
}

문제 링크

풀이 ) DP - LIS

  LIS를 활용한 문제이다. 옮겨지는 아이들을 주목해서 입력 예시인 3 7 5 2 6 1 4 에서 옮겨지는 아이를 다른 색으로 표시하면 3 7 5 2 6 1 4 가 된다.

  이 때 옮겨지는 아이, 즉 붉은색으로 표시된 아이들을 제외하고는 가장 긴 부분 수열을 만족하는 것을 알 수 있다. 가장 긴 부분 수열에서 해당하지 않는 아이만 옮겨주면 된다는 뜻이다.

#include <cstdio>
#include <algorithm>
using namespace std;

int main(void)
{
  int n, arr[201] = {0, }, memo[201], move = 0;
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", arr+i);

  fill(memo, memo+sizeof(memo)/sizeof(int), 1);
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < i; ++j)
      if(arr[i] > arr[j])
        memo[i] = max(memo[i], memo[j]+1);
    move = max(move, memo[i]);
  }
  printf("%d\n", n-move);
}

문제 링크

풀이 ) DP

  길이가 1일 때의 부분 수열의 길이는 1이고,

  2 이상일 때는 앞에서부터 현재 a[1]과 비교하여 a[0]이 더 작다면 memo[0]+1과 memo[1]을 비교하여 더 큰 값을 memo[1]에 넣는다.

  더 큰 수를 예로 들면 길이가 4인 부분 수열에서 a[3]이 a[0], a[1], a[2]와 순차적으로 비교하여 만약 a[0]과 a[2]가 더 작다면 memo[3]은 memo[0]+1과 memo[2]+1 중 더 큰 값을 저장하게 된다.

#include <cstdio>
#include <algorithm>
using namespace std;

int memo[1001] = {1, };

int main(void)
{
  int n, a[1001] = {0, }, ans = 1;
  scanf("%d", &n);
  for(int i = 0; i < n; ++i)
    scanf("%d", a+i);

  for(int i = 1; i < n; ++i){
    memo[i] = 1;
    for(int j = 0; j < i; ++j)
      if(a[i] > a[j])
        memo[i] = max(memo[i], memo[j]+1);
  }
  for(int i = 0; i < n; ++i)
    ans = max(ans, memo[i]);
  printf("%d\n", ans);
}

주의점 )

  모든 부분 수열의 최소 길이는 1이므로 memo[i] = 1을 매 반복문마다 해준다.

문제 링크

풀이 ) DP

  LIS라고 부르는 문제이다.

  앞에서 부터 시작하여 숫자를 하나씩 추가해 나가면서 부분 문자열의 합의 최대를 찾는 문제이다.

  예제 입력을 예로하면 i는 4일 때 memo[4] = arr[4] = 60이다.

  1 100 2 50의 부분 수열을 순회하면서

•   j = 0일 때 1 < 60 이고 61 > 60 이므로 memo[4] = 61 이 된다.
•   j = 1일 때 100 > 60 이므로 다음으로 넘어간다
•   j = 2일 때 2 < 60 이고 63 > 61 이므로 memo[4] = 63 가 된다. ( ∵ memo[2] = 3)
•   j = 3일 때 50 < 60 이고 113 > 63 이므로 memo[4] = 113 가 된다. ( ∵ memo[3] = 53)

  위와 같은 방식으로 수열의 끝까지 간 후 memo[0] 부터 memo[n-1] 중 최댓값을 출력한다.

#include <cstdio>
#include <algorithm>
using namespace std;

int arr[1002], memo[1002];

int main(void)
{
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i)
        scanf("%d", arr+i);

    for(int i = 0; i < n; ++i){
        memo[i] = arr[i];
        for(int j = 0; j < i; ++j){
            if(arr[j] < arr[i])
                memo[i] = max(memo[i], memo[j]+arr[i]);
        }
        ans = max(ans, memo[i]);
    }
    printf("%d\n", ans);
    return 0;
}

주의점 )

  - 반복문 시작 시 매번 memo[i]가 최소 자신을 포함하므로 memo[i] = arr[i]로 값을 넣고 시작한다.