공부흔적

문제 링크

풀이 ) DP

  직사각형의 첫 타일이 2 x 1인 경우와 1 x 2 2개로 시작하는 2가지 경우로 나눌 수 있다.

  2 x 1로 시작하는 경우 뒤에 2 x (n-1) 직사각형을 채우면 되고

  1 x 2로 시작하는 경우 뒤에 2 x (n-2) 직사각형을 채우면 된다.

  점화식은 memo[n] = memo[n-1] + memo[n-2]이다.

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

int memo[1002] = {0, 1, 2, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 3; i <= n; ++i)
        memo[i] = (memo[i-1] + memo[i-2])%10007;
    printf("%d\n", memo[n]);
    return 0;
}

주의점 )

  memo[n]을 구하는 과정에서 모듈러 연산을 해줘야지 정수 오버플로우가 발생하지 않는다.

문제 링크

풀이 ) DP

  앞에 포스팅한 이친수와 같은 풀이이다.

  시작할 수 있는 가짓수는 2가지다. 1로 시작하거나 00으로 시작할 수 있다.

  따라서 점화식 memo[n] = memo[n-1] + memo[n-2]이다.

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

int memo[1000002] = {0, 1, 2, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 3; i <= n; ++i)
        memo[i] = (memo[i-1] + memo[i-2]) % 15746;

    printf("%d\n", memo[n]);
    return 0;
}

문제 링크

풀이 ) DP

  문제에서 주어진 이친수는 01로 끝나거나 0으로 끝날 수 있다.

  01로 끝나는 경우는 n-2자리 이친수의 뒤에 01을 붙인 경우로 볼 수 있고

  0으로 끝나는 경우는 n-1자리 이친수의 뒤에 0을 붙인 경우로 볼 수 있다.

  따라서 이 때의 점화식은 memo[n] = memo[n-1] + memo[n-2]의 꼴이 됨을 알 수 있다.

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

long long memo[92] = {0, 1, 1, };

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 3; i <= n; ++i)
        memo[i] = memo[i-1] + memo[i-2];

    printf("%lld\n", memo[n]);
}

착오 )

  처음에는 끝이 아닌 앞을 보고 시작했었다.

  그런데 이럴 경우 2자리 이상일 때 10으로 시작하기는 하지만

  이후 3번째 자리부터는 0으로 시작할 수 있기 때문에 이전에 구한 값을 이용할 수 없어서 불가능했다.

문제 링크

풀이 ) DP

  1은 연산할 필요가 없으므로 0이고, 2와 3은 각각 2번 1번 연산을 통해서 1이 될 수 있다.

  그 이후인 memo[n]에 대해서는 처음에 memo[n-1] + 1의 값을 저장한 후

  3으로 나누어 떨어진다면 현재 저장된 값과 memo[n/3] + 1의 값을 비교하여 더 적은 값을 memo[n]에 저장한다.

  마찬가지로 2로 나누어 떨어진다면 현재 저장된 값과 memo[n/2] + 1의 값을 비교하여 더 적은 값을 memo[n]에 저장한다.

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

int memo[1000002] = {0, 0, 1, 1};

int main(void)
{
    int n;
    scanf("%d", &n);

    for(int i = 4; i <= n; i++){
        memo[i] = memo[i-1]+1;
        if(i%3==0) memo[i] = min(memo[i], memo[i/3]+1);
        if(i%2==0) memo[i] = min(memo[i], memo[i/2]+1);
    }
    printf("%d\n", memo[n]);
    return 0;
}

문제 링크

풀이 ) 구현

  이 전에 포스팅한 다음 순열을 반대로 적용시키면 된다.

1. 먼저 배열의 뒤부터 두 개씩 비교하여 앞의 숫자가 더 큰 경우가 있는지 확인한다.

  1 2 3 4 5 같이 오름차순으로 정렬된 숫자의 경우 모두 앞의 숫자가 작기 때문에 다음 순열이 존재하지 않아 -1을 출력하고 종료한다.

2. 앞부분의 숫자가 더 큰 부분을 경계로 해서 뒷부분의 숫자 중 앞의 경계 값보다 작은 값을 찾는다.

  3 4 1 2 5의 경우 3 4 | 1 2 5로 나뉘고 뒷부분의 숫자를 뒤부터 앞의 경계 값인 4와 비교한다.

  4 < 5 -> 4 > 2 : break

3. 위에서의 두 값 4와 2의 자리를 바꿔준 다음 뒷부분을 내림차순으로 정렬해준다.

  3 4 | 1 2 5 -> 3 2 | 1 4 5 -> 3 2 | 5 4 1

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

int arr[10001];

bool dec(int a, int b){
    return a>b;
}

int main(void)
{
    int n, i;
    scanf("%d", &n);

    for(i = 0; i < n; ++i)
        scanf("%d", arr+i);

    if(n == 1){
        printf("-1\n");
        return 0;
    }
// 1 start
    for(i = n-1; i > 0; --i)
        if(arr[i-1] > arr[i])
            break;
    if(i == 0)
        printf("-1\n");
// 1 end
// 2 start
    else{
        int j = n-1;
        while(arr[i-1] < arr[j])
            j--;
// 2 end
// 3 start
        swap(arr[i-1], arr[j]);

        sort(arr+i, arr+n, dec);
// 3 end
        for(int k = 0; k < n; ++k)
            printf("%d ", arr[k]);
    }
    return 0;
}

※ next_permutation()와 같이 algorithm 라이브러리의 prev_permutation()을 통해서 쉽게 구할 수 있다.

문제 링크

풀이 ) 구현

  이 문제의 경우 풀이 방법을 몰라서 인터넷 검색을 통해서 풀 수 있었다.

https://en.cppreference.com/w/cpp/algorithm/next_permutation

1. 먼저 배열의 뒤부터 두 개씩 비교하여 앞의 숫자가 더 작은 경우가 있는지 확인한다.

  5 4 3 2 1 같이 내림차순으로 정렬된 숫자의 경우 모두 앞의 숫자가 크기 때문에 다음 순열이 존재하지 않아 -1을 출력하고 종료한다.

2. 앞부분의 숫자가 더 작은 부분을 경계로 해서 뒷부분의 숫자 중 앞의 경계 값보다 큰 값을 찾는다.

  3 2 5 4 1의 경우 3 2 | 5 4 1로 나뉘고 뒷부분의 숫자를 뒤부터 앞의 경계 값인 2와 비교한다.

  2 > 1 -> 2 < 4 : break

3. 위에서의 두 값 2와 4의 자리를 바꿔준 다음 뒷부분을 오름차순으로 정렬해준다.

  3 2 | 5 4 1 -> 3 4 | 5 2 1 -> 3 4 | 1 2 5

#include <cstdio>
#include <algorithm>	// swap()
using namespace std;

int arr[10001];

int main(void)
{
    int n, i;
    scanf("%d", &n);

    for(i = 0; i < n; ++i)
        scanf("%d", arr+i);

    if(n == 1){
        printf("-1\n");
        return 0;
    }
// 1 start
    for(i = n-1; i > 0; --i)
        if(arr[i-1] < arr[i])
            break;
    if(i == 0)
        printf("-1\n");
// 1 end
// 2 start
    else{
        int j = n-1;
        while(arr[i-1] > arr[j])
            j--;
// 2 end
// 3 start
        swap(arr[i-1], arr[j]);

        sort(arr+i, arr+n);
// 3 end
        for(int k = 0; k < n; ++k)
            printf("%d ", arr[k]);
    }
    return 0;
}

※ algorithm 라이브러리의 next_permutation()를 사용하면 더 간단하게 구현할 수 있다.

주의점 )

- 처음 답을 제출할 때 99%에서 틀렸다고 나왔는데 첫 번째 if문에서 처리한 길이가 1인 입력에 대한 예외처리를 해주지 못했기 때문이었다.