Educational Codeforces Round 004. A

A. The Text Splitting

문제

https://codeforces.com/contest/612/problem/A

Problem - A - Codeforces

 

문제 요약

n, p, q를 입력받고 n개 길의 문자를 p, q개 문자들로 쪼개어 그 개수 및 단어들을 출력한다

 

풀이

i) Naive Solution

반복문 돌면서 k = 1, 2, ... 에 대해 ( n - k * p ) % q == 0인 경우를 찾아 첫줄에 k + ( n - k * p ) / q, 둘째줄부터 p단어씩 k개 q단어씩 ( n - k * p ) / q개 출력한다.

이때의 시간복잡도는 대강 O(n)이라 할 수 있다.

 

ii) Faster Solution

조금 더 빠른 방법이 없는가 생각해봤는데

디오판토스 방정식(Diopahntine Equation)이 생각났다.

gcd로 최대공약수를 구해주고 그 역순으로 px+qy=n에 대해 특수해를 구해줄 수 있다.

이때 일반해는 최대공약수가 d일 때

x = x0 + q / d

y = y0 - p / d

가 되고

n이 d의 배수가 아니라면 값이 존재하지 않을 것이다.

또한 x, y 모두 양의 해를 가져야 하므로 둘 중 하나가 음수인 경우 그걸 가장 작은 양수로 바꿨을 때 나머지가 양수인 경우에만 해가 존재한다.

 

사실 출력부 때문에 O(n)이긴 한데 과정이 O(log N)으로 줄었으니 상관없겠다. (사실 디오판토스 방정식 까먹어서 찾아보면서 다 풀고난 후 시간복잡도 안변하는것 보고 슬펐다)

 

소스코드

#include <stdio.h>

int main(){
    int n, p, q;
    char s[1000];
    scanf("%d%d%d\n",&n,&p,&q);
    scanf("%s",s);
    int a, b, c[1000], C=0, t, d, k;
    for(a=p, b=q; a%b; t=a%b, a=b,b=t) c[C++] = a/b; d=b;
    for(a=0, b=1; C; t=a-b*c[--C], a=b, b=t);
    int A=p/d, B=q/d;
    if(n%d) {
        puts("-1");
        return 0;
    }
    a*=n/d;
    b*=n/d;
    if(a<0) {
        k=(-a+B-1)/B;
        a+=B*k;
        b-=A*k;
    }
    if(b<0){
        k=(b-A+1)/A;
        a+=B*k;
        b-=A*k;
    }
    if(a<0 || b<0) {
        puts("-1");
        return 0;
    }
    C=0;
    printf("%d\n",a+b);
    for(int i=0; i<a; puts(""), ++i) for(int j=0; j<p; ++j) printf("%c",s[C++]);
    for(int i=0; i<b; puts(""), ++i) for(int j=0; j<q; ++j) printf("%c",s[C++]);
}