PKU 2551. Ones. [판정:AC]

휴

TLE에 걸릴 줄 알았는데 다행스럽게도 AC받았습니다 :)

int형을 가지고 문제를 풀려고 하면 오버플로우에 걸리기 때문에

큰 수를 저장할 수 있는 구조체 numstring을 만들었습니다

ones함수는 그 구조체에 len개의 1을 저장하는 기능을 하고,

division함수는 구조체를 divisor로 나눈 나머지를 return합니다

main함수에서는

n을 입력받은 후에

최소 1개, 최대 LENBOUND개의 1을 저장하고 있는 구조체로 나누어서 그 나머지가 0이 되었을 때 break문을 타고 빠져나옵니다

참 쉽죠?

#include <stdio.h> #define LENBOUND 10000 #define ARRBOUND 2500 // LENBOUND/4 typedef struct numstring { int length; int digits[ARRBOUND]; // 0000~9999 } numstring; void ones( numstring *pns, int len ) { int i; int j; pns->length = len; for( i = 0; i < ARRBOUND; i++ ) { pns->digits[i] = 0; } j = ARRBOUND - 1; while( len >= 4 ) { pns->digits[j] = 1111; len -= 4; j--; } switch(len) { case 1: pns->digits[j] = 1; break; case 2: pns->digits[j] = 11; break; case 3: pns->digits[j] = 111; break; } } int division( numstring *pns, int divisor ) { int i = ARRBOUND - (pns->length + 3) / 4; int rem = 0; for( ; i < ARRBOUND; i++ ) { pns->digits[i] += (rem * 10000); rem = pns->digits[i] % divisor; } return rem; } void main() { numstring ns; int n; while( scanf("%d", &n) != EOF ) { int i; for( i = 1; i <= LENBOUND; i++ ) { ones(&ns, i); if( division(&ns, n) == 0 ) break; } if( i <= LENBOUND ) { printf("%d\n", i); } } }