[백준/C] 1323번 숫자 연결하기

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

 

 

참고한 블로그

https://khu98.tistory.com/96

[백준OJ] 1323번 숫자 연결하기

정답 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int check[100001] = { 0 };

long long make_digit(int n) {
	long long digit = 0;
	while (n > 0) {
		digit++;
		n /= 10;
	}
	digit = pow(10, digit);
	return digit;
}

int main() {

	int n, k;
	scanf("%d %d", &n, &k);
	long long digit = make_digit(n);

	int cnt = 1;
	int remainder = n % k;
	int flag = 1;
	while (remainder != 0) {
		remainder = (remainder * digit + n) % k;
		if (check[remainder]) {
			flag = 0;
			break;
		}
		check[remainder] = 1;
		cnt++;
	}
	if (flag) {
		printf("%d\n", cnt);
	}
	else {
		printf("-1\n");
	}
	return 0;
}

 

 

 

 

 

시간초과 코드1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int N, K;

	scanf("%d %d", &N, &K);
	int n = N;

	long long int mult = 1;
	int i = 1;
	while (1) {
		if ((N % K) == 0) {
			printf("결과: %d", i);
			exit(1);
		}
		else {
			int hi = 1;
			for (int k = 0; k < i; k++) {
				hi = hi * 10;
			}
			mult += hi;

			N = n;
			N = N * mult;
			printf("%d mult: %d N: %d\n\n", i, mult, N);
			i++;
		}
	}
	/*
	N * 11 (10 + 1)
	N * 111 (100 + 10 + 1)
	N * 1111 (1000 + 100 + 10 + 1)
	*/
}

 

시간초과 코드 2

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 몇 자리 수인지 세는 함수
int digit(int n) {
	int cnt = 0;
	while (1) {
		n = n / 10;
		cnt++;
		if (n <= 0) break;
	}
	return cnt;
}

int main(void) {
	int N, K;
	scanf("%d %d", &N, &K);
	int originalN = N;

	int remainder;		// 나머지
	int cnt = 0;		// 몇 개의 숫자를 이어붙여야 나누어 떨어지는지

	int mult = (int)(pow(10, digit(N)));
	printf("mult: %d\n", mult);

	while (remainder != 0) {
		remainder = N % K;
		cnt++;
		if (remainder == 0) {
			printf("%d", cnt);
			break;
		}
		else {
			N = remainder * mult + originalN;
		}
	}
}