[SW Expert Academy] Code Battle!

이제 코드배틀이 일주일마다 열리는 것 같군요!

무려 다음주 화요일에도 있습니다!

SW Expert Academy의 문제들은 무단 공유가 안되기 때문에 링크로 대체하겠습니다!

4698. 테네스의 특별한 소수

어떻게 풀까?

이게 D3 난이도라는게 약간 믿기지 않았습니다.. ㄷㄷ

생각보다 어렵게 풀은 문제 같은데 말이죠...

어쨌든! 이 문제는 에라토스테네스의 체를 이용하는 방법입니다!

에라토스 테네스의 체의 방법은 간단합니다!

n = 2 부터 돌면서, 2의 배수들을 지워나갑니다.

그리고 2번은 지워진 적이 없기 때문에 소수입니다!

그리고 n=3의 배수들을 지우고, 3은 지워진 적이 없기 때문에 소수..

이런식으로 반복하면 되죠!

여기에 문제는 '특정한 수를 가진 소수'를 찾는 것이 목적이기 때문에,

0~9의 인덱스를 가지는 배열 안에다가 해당 자리수를 가지는 소수를 모두 넣어놓으면,

나중에 해당 수를 가지는 소수를 찾을때 편하게 찾을 수 있겠죠!

그림처럼, 3에는 3을 가지는 소수들인 3과 73, 그리고 여러 소수가 들어있겠죠!

소수의 최대 크기도 10^6이기 때문에 선형으로 소수들을 찾아도 무리가 없습니다!

이렇게 미리 소수들을 정리한 다음에는 A와 B와 특별한 수를 받으면,

해당 특별한 수의 인덱스에서 A보다 작은 수와 B보다 큰 수의 인덱스를 찾으면 두 인덱스를 빼고 더하기 1을 하면 답이 나오겠죠! (이상 이하이므로)

코드

#pragma once
#include<cstdio>
#include<cstring>
 
bool nprime[1000001];
int nums[10][1000001], len[10] = { 0 };
 
void setNum(int n) {
    int mem = n;
    bool cal[10] = { false };
    while (n) {
        if (!cal[n % 10])
        {
            cal[n % 10] = true;
            nums[n%10][len[n % 10]++] = mem;
        }
 
        n /= 10;
    }
}
 
int ubs(int d, int l, int r, int n) {
    int m;
    while (l <= r) {
        m = (l + r) / 2;
 
        if (nums[d][m] <= n) {
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
 
    return l - 1 > 0 ? l - 1 : 0;
}
 
int lbs(int d, int l, int r, int n) {
    int m;
    while (l <= r) {
        m = (l + r) / 2;
 
        if (nums[d][m] < n) {
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
 
    return r + 1 > len[d] ? len[d] : r + 1;
}
 
int main() {
    int tc;
    scanf("%d\n", &tc);
    
    for (int i = 2; i <= int(1e6); i++) {
        for (int j = 2; i*j <= int(1e6); j++) { 
            nprime[i*j] = true;
        }
        if (nprime[i] == false) {
            setNum(i);
        }
    }
 
    for (int t = 1; t <= tc; t++) {
        int D, A, B;
        scanf("%d %d %d\n", &D, &A, &B);
 
        int l = lbs(D, 0, len[D] - 1, A);
        int r = ubs(D, 0, len[D] - 1, B);
 
        printf("#%d %d\n", t, r - l + 1);
    }
    return 0;
}

여담

시간 복잡도는 소수의 인덱스를 찾기위해 이분 탐색을 하기 때문에 O(log(n))이 될 것 입니다!

4699. 콩순이의 가장 싼 팰린드롬

어떻게 풀까?

전형적인 DP 문제입니다!

팰린드롬을 만들기 위해서는 끝에서부터 맞추는 것이 중요하죠!

그리고, 문자열이 없거나 하나만 있다면 무조건 팰린드롬이라는 것이 중요합니다!

그리고, 문제에서는 '한 문자를 삽입하는데 드는 비용'과 '한 문자를 삭제하는데 드는 비용' 두개를 주었습니다.

하지만, 잘 생각해보면, 팰린드롬을 만들기 위해서는 둘 중에서 딱 하나만을 사용하죠!

둘은 결국 똑같은 역할을 하기 때문입니다!

그림에서 처럼 ab를 팰린드롬을 만들기 위한 몇 개의 방법 중에서 하나를 보면,

a를 뒤에 넣는다와 a를 삭제한다! 가 있습니다.

그러면 b라는 팰린드롬을 만들 수 있죠!

즉, 최소의 비용으로 b라는 팰린드롬을 만들기 위해서는 a를 넣는것과 삭제하는 것 중에서 싼 행동을 하면 됩니다!

이렇게 하면 ,팰린드롬을 어떻게 만들지에 대한 전략을 알아낼 수 있습니다.

문자열 사이에 팰린드롬인 것이 있다고 해봅시다!

이 팰린드롬 옆에 a라는 문자열이 있었다면, a문자열 을 팰린드롬 오른쪽에 삽입하거나, a를 삭제해서 팰린드롬을 유지하는 방법이있죠!

이렇게, 인덱스를 하나씩 넓히면서 팰린드롬을 키워갈 수 있습니다.

위처럼 팰린드롬 옆에도 팰린드롬이면, 가격의 증가 없이 바로 인덱스를 넓히고 팰린드롬을 만들 수 있겠죠!

그렇다면 메모이제이션으로 이를 어떻게 나타낼 수 있을까요?

한 문자열의 부분집합을 시작과 끝 인덱스로 나타냅시다.

그리고, 해당 부분집합을 가장 최소의 가격으로 팰린드롬으로 나타내는 가격을 mem[시작 인덱스][끝 인덱스]이라고 하겠습니다!

그리고 인덱스의 문자열을 뒤나 앞에 삽입하거나 삭제하는 가격을 price(인덱스)라고 하죠!

그러면, 위에서 봤던것 처럼, 

mem[시작][끝] = min(mem[시작 + 1][끝] + price(시작), mem[시작인덱스][끝 인덱스 - 1] + price(끝)) 이 되겠죠!

그리고, 시작과 끝에있는 글자가 같다면, mem[시작][끝] = min(... , mem[시작 +1][끝 - 1])도 추가해야할 것입니다!

팰린드롬이 시작되는 부분은 시작과 끝이 같은 부분들이 되겠죠! 한 글자인 부분이니까요. 

그리고 시작인덱스가 끝 인덱스보다 큰 곳은 빈 문자열이라고 생각하고 0으로 채웁니다.

코드

#include<cstdio>
#include<cstring>
 
 
int n, k, memoi[2001][2001] = { 0 }; // start, end;
int price['z' + 1];
char str[2001] = { 0 };
 
int min(int i1, int i2) {
    return i1 < i2 ? i1 : i2;
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
    
    for (int tc = 1; tc <= t; tc++) {
 
        scanf("%d %d\n", &n, &k);
        scanf("%s\n", str);
        
        int i1, i2;
        
        for (int i = 0; i < k; i++) {
            scanf("%d %d\n", &i1, &i2);
 
            price[i + 'a'] = i1 < i2 ? i1 : i2;
        }
 
        for (int i = 0; i < n; i++) {
            memoi[i][i] = 0;
            for (int j = i+1; j < n; j++) {
                memoi[i][j] = 987654321;
            }
        }
 
        for (int k = 1; k < n; k++) {
            int i = 0, j = k;
 
            for (int l = 0; l < n - k; l++) {
                memoi[i][j] = min(memoi[i][j], memoi[i + 1][j] + price[str[i]]);
                memoi[i][j] = min(memoi[i][j], memoi[i][j - 1] + price[str[j]]);
                if (str[i] == str[j]) memoi[i][j] = min(memoi[i][j], memoi[i + 1][j - 1]);
                i++; j++;
            }
        }
        
        printf("#%d %d\n", tc, memoi[0][n-1]);
    }
    return 0;
}
 

여담

시간 복잡도는 주어진 문자열의 길이가 n이라고 한다면, O(n^2)이 됩니다!

그리고.. 이 문제는 재귀 DP로 풀었는데.. 이상하게 정답이 안풀려서 결국 코드 배틀에서는 한 문제만 풀었네요 ㅠㅠㅠㅠ

아쉽습니다...