#73. [백준_C언어] 12971 : 숫자 놀이 \ 수학

 

입력 코드

#include <stdio.h>

main() {
	int P1, P2, P3, X1, X2, X3, N;
	scanf("%d %d %d %d %d %d", &P1, &P2, &P3, &X1, &X2, &X3);

	int ans = -1;
	for (N = 1; N <= P1*P2*P3; N++) {
		if ((N%P1 == X1) && (N%P2 == X2) && (N%P3 == X3)) {
			ans = N;
			break;
		}
	}
	printf("%d\n", ans);
}

 

 

코드 설명

#수학 #브루트포스알고리즘 #정수론 #중국인의나머지정리

 

처음에는 N을 1,000,000,000까지 탐색하려고 했는데 그렇게 하면 시간 초과가 발생해버린다.

 

N=1일 때 X1, X2, X3는 모두 1일 것이다.

N이 계속 증가하다가 N=P1*P2*P3가 되면 X1, X2, X3는 모두 0일 것이다.

그리고 N=P1*P2*P3+1이 되면 다시 X1, X2, X3=1이 된다.

 

그래서 N <= P1*P2*P3까지만 탐색하면 된다.

 

 

 

참고

ip99202.github.io/posts/%EB%B0%B1%EC%A4%80-12971-%EC%88%AB%EC%9E%90-%EB%86%80%EC%9D%B4/

백준 12971 숫자 놀이 java

 

 

문제 출처

www.acmicpc.net/problem/12971

12971번: 숫자 놀이