Archive

수학의 연산자뿐만 아니라 프로그래밍 언어의 연산자 역시 우선순위라는 개념이 존재한다. 이는 여러 가지 연산자가 포함된 수식에서 어떤 연산자를 먼저 연산해야 하는지를 지칭하는 순서이다. 우선순위가 정의되는 경우 일반적으로 두 연산자의 우선순위 관계는 불변이므로, 임의의 개수의 연산자에 대해 우선순위가 높은 순서대로 1-based index를 매길 수 있다.

FORTRAN I Compiler는 우선순위의 index를 이용하여 연산자의 연산 순위를 올바르게 반영하는 parenthesized string으로 연산식을 치환한다. 이는 우선순위 정보를 갖고 있지 않더라도 식을 평가할 수 있게 하며, 연산식 파싱을 간단한 괄호 문자열 스위핑 문제로 환원한다. 그 구체적인 알고리즘은 다음과 같이 서술할 수 있다.

1. 연산자의 우선순위가 높은 순서대로 1-based index를 부여한다. 임의의 두 연산자가 서로 우선순위가 같다면 같은 index가 부여되어도 무관하다. index가 부여된 연산자 $*$의 해당 index를 $I_*$라 하자. 또한 $M=\displaystyle\max_{\forall \text{operator }*}I_*$으로 $M$을 정의하자.
2. 연산식을 한 쌍의 괄호로 감싼다.
3. $($과 $)$를 각각 $\overbrace{((...(}^{M+1}$과 $\overbrace{))...)}^{M+1}$로 치환한다.
4. 모든 연산자 $*$에 대해 연산식 내의 $*$를 $\overbrace{))...)}^{I_*}*\overbrace{((...(}^{I_*}$로 치환한다.

$1+(2*3+4)*5$를 예시로 알고리즘을 적용해보자.

1. $I_*=1,I_+=2,M=2$
2. $(1+(2*3+4)*5)$
3. $(((1+(((2*3+4)))*5)))$
4. $(((1))+(((((2)*(3))+4))))*(5)))$

알고리즘의 결과로 $(((1))+(((((2)*(3))+4))))*(5)))$라는 수식을 얻을 수 있고, 이는 괄호만으로 원래의 연산자 계산 순서를 보장하는 문자열이다.

과연 이 알고리즘은 항상 올바른 괄호 문자열, 그것도 연산자 계산 순서를 동일하게 보장하는 문자열을 생산할까? 

Lemma 1. 입력에 괄호가 없을 경우 알고리즘은 올바른 괄호 문자열을 생산한다.

수식을 순서대로 읽을 때 $($의 개수에서 $)$의 개수를 뺀 값을 $P$라 하자. 알고리즘의 2번 단계에서 추가된 괄호에 의해 초기에 $P$는 $M+1$이다.

$M$의 정의에 의해 각각의 연산자가 치환 후 그 직전에 갖는 $)$의 개수는 $M$개 이하이므로 모든 시점에서 $P$는 1 이상이다. 또한 $*$가 치환된 $\overbrace{))...)}^{I_*}*\overbrace{((...(}^{I_*}$는 각각 ${I_*}$개의 $($과 $)$를 포함하므로 치환된 문자열을 처리하기 전과 후의 $P$는 동일하다. 따라서 각각의 연산자를 처리하며 $P$는 최소 1의 값을 가지며 마지막 $M+1$개의 $)$ 처리하기 직전에는 $P=M+1$이다. 따라서 수식을 전부 처리하면 $P=0$이므로 알고리즘의 출력은 올바른 괄호 문자열이다.

Lemma 2. 입력이 올바른 수식일 경우 알고리즘은 올바른 괄호 문자열을 생산한다.

입력에 괄호가 없는 경우는 Lemma 1에서 증명하였으므로 입력에 괄호가 존재하는 경우를 증명하자.

입력된 수식은 유한하므로, 양끝에 각각 하나의 $($와 $)$를 가지며 이외에는 괄호를 포함하지 않는 부분 수식 $(S)$를 고를 수 있다. 그렇지 않은 경우 무한히 부분 수식을 택하여 무한한 $($와 $)$가 문자열에 포함되어 수식이 유한한 길이를 갖는다는 조건에 모순된다.

이때 $(S)$가 치환된 문자열은 입력에 괄호가 없는 수식 $S$가 알고리즘에 입력됐을 때의 출력과 동일하다. Lemma 1에 의해 $(S)$가 치환된 문자열은 올바른 괄호 문자열이다.

즉 $(S)$가 치환된 문자열의 전후에서 $P$의 값이 동일하며, Lemma 1의 증명에서 언급한 것과 같이 연산자가 치환된 문자열에 의해서는 괄호 문자열이 올바르지 않게 될 수 없다. 따라서 귀납적으로 알고리즘의 전체 출력은 올바른 괄호 문자열이다.

Lemma 3. 입력에 괄호가 없을 경우 알고리즘은 연산 순서가 유지된 수식을 생산한다.

연산자가 위치한 곳에서의 $P$ 값이 높을수록 알고리즘의 출력 수식의 expression tree에서 depth가 깊다. 즉, $P$ 값이 높은 연산자일수록 먼저 계산된다. $P$ 값이 동일하며 우선순위가 서로 다른 연산자가 존재한다면 이 성질은 성립하지 않을 수 있지만, 알고리즘에 의하여 입력에 괄호가 없을 경우 어떤 연산자 $*$에서의 $P$는 $M+1-I_*$이기 때문에, 우선순위가 서로 다른 연산자는 서로 다른 $P$ 값을 가진다. 즉 위 성질이 성립하여 연산자 우선순위가 괄호에 의해 보존되게 된다.

Theorem 1. 입력이 올바른 수식일 경우 알고리즘은 연산 순서가 유지된 수식을 생산한다.

Lemma 2와 마찬가지로 양끝에 각각 하나의 $($와 $)$를 가지며 이외에는 괄호를 포함하지 않는 부분 수식 $(S)$를 고를 수 있다. $(S)$가 치환된 문자열은 입력이 $S$일 때의 Lemma 3를 적용할 수 있다. 이후 $(S)$를 포함하는 $(S)$가 아닌 최소 길이의 부분 수식 $(T)$에 대해, $(S)$는 하나의 상수 $C$로 치환하여도 수식 $(T)$의 치환 전후 연산 순서 동일성에 영향을 주지 않는다(괄호 내부는 원래 먼저 계산하므로). 따라서 $(T)$에 포함된 모든 $(S)$들을 어떤 상수로 치환하면 Lemma 3에 의해 $(T)$ 역시 치환 전후의 연산 순서가 변화하지 않는다. 이러한 논리를 귀납적으로 적용하면 입력 전체에 대해 연산 순서가 치환 전후로 변화하지 않는다는 것을 알 수 있다.

따라서 Theorem 1에 의해, 위 알고리즘은 항상 의도한 바대로 동작함을 알 수 있다.

https://www.acmicpc.net/problem/2727

Ad-hoc스러운 문제인 만큼, 풀이를 알면 쉬우나 풀이를 떠올리는 것이 조금 어려운 문제이다.

핵심 아이디어는 다음의 두 가지이다.

1. 임의의 자연수는 어떤 홀수 $x$와 어떤 정수 $k$에 대해 $2^k\times x$꼴로 표현된다. 특히, 짝수에 대해서는 $k$는 1 이상이다.

2. 3의 거듭제곱(1 포함)을 홀수에서 빼면 짝수가 된다.

위의 두 가지 사실을 이용하여 문제를 풀어보자.

1번에 의해 임의의 입력을 홀수로 변형할 수 있으며($N^\prime=N/2^k$), 홀수의 경우에는 2번에 의해 다시 짝수로 만들어줄 수 있다.($N^\prime=N-3^k$)

이 과정을 반복하여 문제를 해결할 때, $N$은 $2^{a_1}(3^{b_1}+2^{a_2}(3^{b_2}+...))$의 꼴로 표현된다. 모두 전개하면 $2^{a_1}3^{b_1}+2^{a_1+a_2}3^{b_2}+...$과 같이 표현된다는 사실을 알 수 있을 것이다. 이는 문제에서 요구하는 각각의 항과 동일한 꼴임을 발견할 수 있다.

이제 중요한 것은 이러한 항들이 문제 조건을 만족하는가이다. 즉, 2의 지수가 증가하는 순으로 나열했을 때 3의 지수를 감소하게끔 설정할 수 있는지가 핵심이 될 것이다.

$3^{b_i}$에 곱해진 2의 거듭제곱의 지수는 증가함이 자명하다. $a_1\le0$이며, 위의 2번 사실에 의해 2 이상의 정수 $i$에 대해 $a_i>0$이기 때문이다. 그렇다면 $b_i$가 감소수열이기만 하면 이렇게 구한 항들은 문제의 정답에 해당할 것이다.

여기서, 우리는 $b_i$의 값을 확정하지 않았음을 상기하자. 따라서 감소수열 $b_i$를 적당히 정의하기만 하면 된다. 가장 무난하며 쉽게 찾을 수 있는 선택지는 선택할 수 있는 가장 큰 3의 거듭제곱이다. 이 정의의 경우 $b_i$가 단조감소한다는 사실은 3진법 전개를 통해 쉽게 증명할 수 있으므로 독자에게 맡긴다.

위와 같은 풀이를 재귀함수 내지는 반복문을 이용하여 구현하면 AC를 받을 수 있다. 아래는 이를 구현한 코드이다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

void TC(){
    ll n;
    cin>>n;
    int b2=0;
    vector<int> v,w;
    while(n>0){
        while(n%2==0){
            b2++;
            n/=2;
        }
        ll r=1;
        int i;
        for(i=0;r<=n;i++,r*=3);
        r/=3;i--;
        n-=r;
        v.push_back(b2);
        w.push_back(i);
    }
    cout<<v.size()<<"\n";
    for(int i=0;i<v.size();i++){
        cout<<v[i]<<" "<<w[i]<<"\n";
    }
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    int tc;
    cin>>tc;
    while(tc--){
        TC();
    }
}

https://www.acmicpc.net/problem/1078

자릿수에 관한 관찰이 필요한 문제이다. 따라서 0-based index로 $i$번째 자릿수를 $a_i$로 정의하는 것이 문제 풀이에 도움이 될 것이다.

이때 문제의 정답이 되는 최소의 자연수를 $X$, $X$를 뒤집은 수를 $\bar{X}$, $X$의 길이를 $L$이라 하자. 정의에 의해 다음의 세 가지 식이 성립한다.

1. $\displaystyle X=\sum_{i=0}^{L-1}a_i\times10^{i}$

2. $\displaystyle \bar{X}=\sum_{i=0}^{L-1}a_i\times10^{L-i}$

3.  $X-\bar{X}=D$

1,2번 식을 3번 식에 대입하여 정리하면 다음과 같은 식을 얻을 수 있다.

$$\sum_{i=0}^{\lfloor L/2\rfloor}(a_{L-i-1}-a_{i})\times10^{i}\times(10^{L-2i}-1) = D$$

여기서 임의의 음이 아닌 정수 $k$에 대해 $10^k \mod 9 = 1$이라는 사실을 떠올려보자. 양변을 9로 나눈 나머지를 취해보면, 좌변은 나머지가 0이므로 $D$ 역시 9로 나눈 나머지가 0이 되어야 한다. 그렇지 않은 경우 우측과 같은 표현법이 존재하지 않아 $X$와 $\bar{X}$가 존재하지 않음을 확인할 수 있다.

다만, $D$가 9의 배수라고 항상 이러한 표현법이 존재한다고 이야기할 수는 없다. 실제로 $D$로부터 $X$를 찾는 과정에서 그 조건을 더 자세히 확인해보자.

우리는 $D$가 9의 배수임을 확인하였으므로 자연수 $D^\prime=D/9$를 얻을 수 있다. $-9\le a_{L-i-1}-a_{i}\le9$, $10^{L-2i}-1=1111....111$이므로 $D^\prime \mod 10$은 $a_{L-1}-a{0}$와 같다. 이러한 성질을 이용하여 $i$를 점점 증가시키며 $a_{L-i-1}-a_i$를 구할 수 있다. 이 값을 구했을 때 부호에 따라 적절히 처리해주면 최소의 $X$를 구할 수 있다. 모든 $i$에 대해 시행한 후에 $D$가 0이 아니라면 $X$가 존재하지 않는다는 것을 알 수 있다.

위의 모든 풀이가 정답의 길이 $L$을 알 때 사용할 수 있는 풀이이나 $L$의 범위는 굉장히 작다는 점이다. 따라서 작은 $L$부터 증가하는 순서대로 시도하여 답을 구할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

ll ipow(ll a,int n){
    if(n==0)return 1;
    if(n==1)return a;
    if(n==2)return a*a;
    ll res = ipow(a*a,n/2);
    if(n%2)res *= a;
    return res;
}

ll f(ll D,int l){
    ll res = 0;
    ll Dp=D;
    for(int i=0;2*i<l;i++){
        if(D%10>0||(D%10==0&&i!=0))res += D%10*ipow(10,l-i);
        if(D%10==0&&i==0)res += ipow(10,l-i)+(l-i!=i)*ipow(10,i);
        if(D%10<0)res -= D%10*ipow(10,i);
        D-=D%10*(ipow(10,l-2*i)-1)/9;
        D/=10;
    }
    if(D)return -1;
    else return res;
}

int main(void){
    ios::sync_with_stdio(0);cin.tie(0);
    ll D;
    cin>>D;
    if(D%9){
        cout<<"-1";
        return 0;
    }
    D/=9;
    for(int i=1;i<=17;i++){
        ll r = f(D,i);
        if(r!=-1){
            cout<<r;
            return 0;
        }
    }
    cout<<"-1";
    return 0;
}

https://www.acmicpc.net/problem/9556

매겨진 난이도가 높지만 아이디어가 어려운 문제는 아니다. 다음의 필요한 사전 지식을 안다면 쉽게 해결할 수 있다.

1. 분할 정복을 이용한 거듭제곱 - 티어 올린 주범인 듯 하다. 알면 쉬움.

2. 페르마 소정리 - 페르마 소정리 자체를 알지 못해도, 거듭제곱이 mod n에서 주기성을 가진다는 사실을 이해하면 충분하다.

우선은 1, 2, 3, 4, 5, 6의 배수인지 여부가 문제 정답에 큰 기여를 한다는 사실은 자명하다. 따라서 이들의 최소공배수를 구하자면 60이다. 이 60을 주기로 하여 반복된 패턴이 나타남을 예상할 수 있다. 필자는 최소공배수를 120으로 착각하여 풀이하였으나, 충분히 작은 공배수라면 어떤 것을 사용하여도 무관하다. 후술할 풀이에서는 주기를 120으로 사용한다.

120을 주기로 답에 포함이 되는 수인지 여부가 반복된다는 사실을 관찰하였다. 따라서 문제에서 제시된 $10^n$ 미만의 자연수 또는 0에 과연 몇 개의 주기가 들어가는지 확인하기 위하여 $10^n$을 120으로 나누어보자. $n$의 값이 1, 2, 3,...이 됨에 따라 $10^n$은 $120\times0+1,120\times0+10,120\times0+100,120\times8+40,120\times83+40,...$으로 표현됨을 확인할 수 있다.

즉, $n$이 3 이상이면 $10^n \mod 120 = 40$이 성립한다는 뜻이다. 이를 수학적 귀납법으로 증명할 수 있다. $10^n=120x+40$을 만족하는 정수 $x$가 존재한다고 가정하자. 이때 $10^{n+1}=10\times(120x+40)=1200x+400=120\times(10x+3)+40$이므로, $10^{n+1}$ 역시 120으로 나눈 나머지가 40이다. $n=3$일 때부터 해당 가정이 성립하므로 수학적 귀납법에 의하여 $n$이 3 이상일 때 $10^n \mod 120$은 40이다.

또 한 가지 위의 과정에서 관찰할 수 있는 사실은, $10^n$을 120으로 나눈 몫이 $a_n$이라 할 때, $a_{n+1}=10a_n+3$이 성립한다는 사실이다. 만약 $a_n$을 구할 수 있다면 0 이상 120 미만의 정수 중 입력 조건을 만족하는 정수의 수 $s$, 0 이상 40 미만의 정수 중 입력 조건을 만족하는 정수의 수 $t$에 대하여 정답은 $s\times a_n+t$임을 쉽게 알 수 있다. 이러한 논리 흐름을 풀이에 적용하기 위하여 $a_n$을 빠르게 구해야 하며 이는 행렬 곱셈을 활용하여 해결 가능하다.

$a_{n+1}=10a_n+3$ 꼴의 점화식을 계산하는 것은 다음 식을 통해서도 가능하다. 성립 여부는 우변을 직접 계산하면 점화식에 의해 좌변과 같이 정리할 수 있음을 통해 확인할 수 있다.

$$\begin{bmatrix}a_{n+1} \\1\end{bmatrix} = \begin{bmatrix}10 & 3 \\0 & 1\end{bmatrix}\times\begin{bmatrix}a_{n} \\1\end{bmatrix}$$

따라서 다음과 같이 행렬 거듭제곱에 관한 식으로 표현하면 분할 정복을 활용하여 쉽게 4 이상의 $n$에 대해 $a_n$을 계산할 수 있다.

$$\begin{bmatrix}a_{n} \\1\end{bmatrix} = \begin{bmatrix}10 & 3 \\0 & 1\end{bmatrix}^{n-3}\times\begin{bmatrix}a_{3} \\1\end{bmatrix}$$

이후에는 위에서 서술한 바와 같이 $s\times a_n+t$를 출력하면 된다. 더불어 해당 풀이는 $n$이 4 이상일 때 구현하기 쉬우므로, $n$이 3 이하일 때는 brute force를 활용하여 답을 구하도록 하면 깔끔하게 문제를 해결할 수 있다.

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const ll MOD = 1000000007;

ll ipow(ll a,ll n,const int mod){
    if(n==1)return a;
    if(n==2)return 1ll*a*a%mod;
    ll res=ipow(a*a%mod,n/2,mod);
    if(n%2)res=res*a%mod;
    return res;
}

struct matrix{
    ll a,b;
    ll c,d;
    matrix operator*(const matrix t){
        return {(a*t.a%MOD+b*t.c%MOD)%MOD,(a*t.b%MOD+b*t.d%MOD)%MOD,(c*t.a%MOD+d*t.c%MOD)%MOD,(c*t.b%MOD+d*t.d%MOD)%MOD};
    }
};

matrix mpow(matrix a,ll n){
    if(n==0)return {1,0,0,1};
    if(n==1)return a;
    if(n==2)return a*a;
    matrix r=mpow(a*a,n/2);
    if(n%2)r=r*a;
    return r;
}

void tc(){
    ll n;
    scanf("%lld",&n);
    if(n<=3){
        int x[7];
        for(int i=1;i<=6;i++){
            scanf("%1d",&x[i]);
        }
        int cnt=0;
        for(int i=0;i<(n==1?10:(n==2?100:1000));i++){
            int c=0;
            for(int j=1;j<=6;j++){
                c+=((x[j]==0&&i%j!=0)||(x[j]==1&&i%j==0)||(x[j]==2));
            }
            cnt+=(c==6);
        }
        printf("%d\n",cnt);
        return;
    }
    int arr[120]={1,};
    for(int i=0;i<120;i++)arr[i]=1;
    for(int i=1;i<=6;i++){
        int x;
        scanf("%1d",&x);
        if(x==0){
            for(int j=0;j<120;j++)if(j%i==0)arr[j]=0;
        }
        if(x==1){
            for(int j=0;j<120;j++)if(j%i!=0)arr[j]=0;
        }
    }
    matrix m = mpow({10,3,0,1},n-3);
    ll r = (m.a*8+m.b)%MOD;
    ll x1=0, x2=0;
    for(int i=0;i<120;i++){
        x1+=arr[i];
    }
    for(int i=0;i<40;i++){
        x2+=arr[i];
    }
    printf("%lld\n",(x1*r%MOD+x2)%MOD);
}

int32_t main(void){
    int TC;
    scanf("%d",&TC);
    while(TC--){
        tc();
    }
}