[SW Expert Academy] Code battle!

오늘은 약 1 ~ 2 주마다 SW Expert Academy에서 시행하는 Code Battle! 문제를 풀었습니다.

D3 ~ D7 사이의 문제가 골고루 출제되는 듯 합니다.

현재 상황.

SW Expert Academy의 문제는 함부로 공유하지 말라고 명시되어 있으므로, 링크를 올리겠습니다.

4522. 세상의 모든 팰린드롬

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWO6Oao6N4QDFAWw&categoryId=AWO6Oao6N4QDFAWw&categoryType=CODE

우선, 펠린드롬이란, 앞에서 읽어도 뒤에서 읽어도 같은 단어를 의미합니다.

이 문제에서는 '?' 단어가 나오면, 신경 쓰지 않고 무조건 펠린드롬을 만들 수 있다고 하고 맨 뒤와 맨 앞 문자를 비교하면서 가운데까지 올 수 있는지 보면 됩니다.

아래는 코드입니다!

#pragma once
#include<cstdio>
 
int getSize(char* str)
{
    int i = 0;
    while (str[i])
    {
        ++i;
    }
    return i;
}
 
bool check(char *str, int size)
{
    for (int i = 0; i < (size >> 1); i++)
    {
        if (str[i] == '?' || str[size - i - 1] == '?') continue;
 
        if (str[i] != str[size - 1 - i]) return false;
    }
    return true;
}
 
int main()
{
    int t;
    scanf("%d\n", &t);
 
    const char res[2][11] = { "Not exist", "Exist" };
    for (int tc = 1; tc <= t; tc++)
    {
        char str[21];
 
        scanf("%s\n", str);
 
        printf("#%d %s\n", tc, res[check(str, getSize(str))]);
    }
 
    return 0;
}

4530. 극한의 청소 작업

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWO6cgzKOIEDFAWw&categoryId=AWO6cgzKOIEDFAWw&categoryType=CODE

문제의 핵심을 '4'가 들어가는 개수를 구하는 것이라고 생각했고, 이에 초점을 맞추어서 구했습니다.

알고리즘은 DP를 이용했습니다.

숫자가 n 자리 수이면, n 자리 수에서 4가 포함되는 경우는 다음과 같이 나타낼 수 있습니다.  

1. n - 1 자리 수에서 4가 들어가는 수 앞에 0, 1, 2, 3, 5, 6, 7, 8, 9를 넣습니다.

2. 맨 앞에 4를 넣고 0 ~ 10^(n) - 1 을 넣습니다.

즉, 맨 앞의 숫자가 4가 아니라면 n - 1 자리수 에서 4가 들어가는 모든 경우의 수를 더해주면서 DP를 만들어 나갑니다. (2 차원 배열)

예로 1 자리 수를 생각해보겠습니다. 우선 1 ~ 9 에서 만들어질 수 있는 4가 들어갈 수 있는 수는 { 0, 0, 0, 1, 1, 1, 1, 1, 1 } 가 될 것입니다.

2 자리 수의 경우에는 1X , 2X, 3X, 4X, 5X, 6X, 7X, 8X, 9X 입니다. 

10 미만 = 1번 째 자리에서 만들 수 있는 4의 개수 = 4

20 미만 = 4, 14 

30 미만 = 4, 14, 24 

40 미만 = 4, 14, 24, 34

50 미만 = 4, 14, 24, 34, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49

...

이므로 

{1, 2, 3, 4, 14, 15, 16, 17 ,18 } 이 될 것입니다. 

그렇다면 321 같은 수의 개수는 어떻게 구하면 될까요?

300 이하에서의 4의 개수를 구하고

300보다 크고 320 이하에서의 4의 개수를 구하고 (앞에서 3을 제외하고 2X 에서의 4가 들어가는 개수를 보면 됩니다!)

320보다 크고 321 이하에서의 개수를 구하면 된다! (마찬가지로 앞의 3, 2를 제외하고 1이하에서의 4의 개수를 보면 됩니다!)

그리고 그 값을 모두 더해주면 됩니다!

이는, 각 자리수마다 앞자리 수에 대한 DP값을 모두 더해주면 됩니다.

재귀 함수로 구현했지만, while문을 이용하는 방법도 있을 것입다.

나머지는 부호에 따라서 적절히 처리해 주면 됩니다.

#pragma once
// SWEA ������ û�� �۾� : https://www.swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AWO6cgzKOIEDFAWw&categoryId=AWOuXSOaAEgDFAWw&categoryType=BATTLE
#include<cstdio>
 
long long fourNum[13][10] = { 0 };
 
int getDigit(long long n)
{
    int len = 0;
 
    while (n)
    {
        len++;
        n /= 10;
    }
 
    return len;
}
 
long long abss(long long ll)
{
    return ll > 0 ? ll : -ll;
}
 
long long getCnt(long long ll, int len, long long digit, long long sum)
{
    if (len == 0)
    {
        return sum;
    }
 
    int cnt = ll / digit;
 
    long long res = 0;
 
    res += fourNum[len][cnt];
 
    return getCnt(ll % digit, len - 1, digit / 10, sum + res);
}
 
int main()
{
    long long digit = 1;
    for (int i = 1; i < 13; i++)
    {
        fourNum[i][1] = fourNum[i - 1][9] + fourNum[i - 1][1];
 
        for(int j = 2; j < 10; j++)
        {
            if(j == 5)
            {
                fourNum[i][j] += fourNum[i][j - 1] + digit;
                continue;
            }
            fourNum[i][j] = fourNum[i][j - 1] + fourNum[i][1];
        }
 
        digit *= 10;
    }
 
    int t;
 
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        long long ll1, ll2;
        scanf("%lld %lld\n", &ll1, &ll2);
 
        long long res;
 
        int len1 = getDigit(abss(ll1));
        int len2 = getDigit(abss(ll2));
 
        long long digit1 = 1, digit2 = 1;
 
        for (int i = 1; i < len1; i++)
        {
            digit1 *= 10;
        }
 
        for(int i = 1; i < len2; i++)
        {
            digit2 *= 10;
        }
 
        if (ll1 >> 63 ^ ll2 >> 63)
        {
            res = ll2 - ll1 - getCnt(ll2, len2, digit2, 0) - getCnt(abss(ll1), len1, digit1, 0);
            res--;
        }
 
        else
        {
            res = ll2 - ll1;
            res -= abss(getCnt(abss(ll1), len1, digit1, 0) - getCnt(abss(ll2), len2, digit2, 0));
        }
 
        printf("#%d %lld\n", tc, res);
    }
    return 0;
}

4534. 트리 흑백 색칠

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWO6esOKOKQDFAWw&categoryId=AWO6esOKOKQDFAWw&categoryType=CODE

위 문제에서 주목한 점은 n개의 노드와 n - 1 개의 간선, 그리고 무조건 트리 형식이 된다는 것입니다.

다른 말로 하면 모든 정점이 이어지는 스패닝 트리가 된다는 것입니다!

그리고 두 간선으로 이어진 노드 사이의 흑과 백을 칠하는 방법은 다음과 같습니다.

1. 부모가 검정으로 칠해질 경우.

  두 노드 모두 검정이 될 수 없으므로, 현재 부모가 검정으로 칠해질 수 있는 모든 경우 * 자식이 하얀색으로 칠해질 수 있는 모든 경우가 됩니다.

2.부모가 하양으로 칠해질 경우.

 자식이 어떤 색이 되어도 상관 없으므로 현재 하양으로 칠해질 수 있는 모든 경우 * 자식이 칠해질 수 있는 모든 경우 가 됩니다.(흰색 + 백색의 합)

따라서, 하나의 노드를 루트로 삼아서 스택을 이용해 그래프를 방향성을 가진 트리 형식으로 바꾸어 준 다음에 위상 정렬을 사용해 위의 공식을 이용해서 DP를 풀어주면 문제가 풀리게 됩니다!

우선 노드 마다 흰색으로 칠해질 경우와 검은색으로 칠해질 경우를 저장할 공간을 만듭니다.

N : 칠할 수 있는 경우의 수

p : 부모, c : 자식

이라고 하고 위의 공식을 이용하면, 

Np(검) = Np(검) * Nc(흰)

Np(흰) = Np(흰) * (Nc(흰) + Nc(검))이 됩니다!

참고로, 처음에는 모든 노드가 검정색으로 칠해질 경우와 하양으로 칠해질 경우를 1로 초기화 하면 됩니다.

#pragma once
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
 
using namespace std;
 
long long nodes[100001][2];
int deg[100001];
int que[100000];
int sta[100000];
vector<int> adj[100001];
int dir[100001];
 
void init(int n)
{
    memset(deg, 0, sizeof(deg));
    memset(dir, 0, sizeof(dir));
 
    for (int i = 1; i <= n; i++)
    {
        nodes[i][0] = nodes[i][1] = 1;
        adj[i].clear();
        adj[i].resize(0);
    }
}
 
int main()
{
    int t;
    const long long limit = 1000000007;
 
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++)
    {
        int n, st, dt;
        int fr = 0, re = 0;
 
        scanf("%d\n", &n);
 
        init(n);
 
        for(int i = 1; i < n; i++)
        {
            scanf("%d %d\n", &st, &dt);
            adj[st].push_back(dt);
            adj[dt].push_back(st);
        }
 
        int top = 0;
        sta[top++] = 1;
 
        dir[1] = -1;
        while (top)
        {
            int node = sta[--top];
 
            for (int i = 0; i < adj[node].size(); i++)
            {
                int next = adj[node][i];
 
                if (dir[next]) continue;
 
                sta[top++] = next;
                dir[next] = node;
                deg[node]++;
            }
        }
 
        for (int i = 1; i <= n; i++)
        {
            if (deg[i] == 0)
            {
                que[re++] = i;
            }
        }
 
        while (true)
        {
            int node = que[fr++];
 
            if (node == 1) break;
 
            //next
            int next = dir[node];
 
            if(--deg[next] == 0)
            {
                que[re++] = next;
            }
 
            nodes[next][0] *= nodes[node][1] % limit;
            nodes[next][0] %= limit;
 
            nodes[next][1] *= (nodes[node][0] + nodes[node][1]) % limit;
            nodes[next][1] %= limit;
        }
 
        printf("#%d %lld\n", tc, (nodes[1][0] + nodes[1][1]) % limit);
    }
 
    return 0;
}

결과는!! 두둥!

4위~!