[백준] 1145. 적어도 대부분의 배수

: solved.ac - bronze 1

 

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

1145번: 적어도 대부분의 배수

 

 

 

예제 입력 1

30 42 70 35 90

 

예제 출력 1

210

 

예제 입력 2

1 2 3 4 5

 

예제 출력 2

4

 

예제 입력 3

3 14 15 92 65

 

예제 출력 3

195

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int num[5] = { 0 };
	int n = 1, cnt = 0;

	for (int i = 0; i < 5; i++) {
		scanf("%d", &num[i]);
	}

	while (1) {
		for (int i = 0; i < 5; i++) {
			if (n % num[i] == 0) cnt++;
		}

		if (cnt >= 3) {
			printf("%d", n);
			break;
		}
		else {
			cnt = 0;
			n++;
		}
	}

	return 0;
}

---

해설

: 브루트포스(brute force) 알고리즘을 사용한다.

= 1부터 시작해 모든 수를 주어진 다섯 개의 수로 나누어 보면서

3번 이상 나누어떨어지면 그 수를 출력하고 탐색을 멈춘다.

 

(처음 이 문제를 맞닥뜨리면 소인수분해를 하거나 다섯 수의 약수를 동시에 구하는 등 '똑똑한' 해결책을 생각하려 들 수 있지만,(나도 그랬다) 의외로 이 방법이 가장 현명한 방법이다. 젯수로 주어지는 수들이 크지 않고 많지 않으며, 어차피 계산은 컴퓨터가 하기 때문이다.)

 

 

1. 다섯 칸짜리 배열을 선언해 입력값 5개를 받는다.

굳이 배열일 필요는 없으나, 배열인 편이 이후 반복문을 돌리기 편해진다.

변수 n은 피젯수이며(1부터 증가), cnt는 나누어떨어진 횟수를 담을 변수이다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int num[5] = { 0 };
	int n = 1, cnt = 0;

	for (int i = 0; i < 5; i++) {
		scanf("%d", &num[i]);
	}
	//배수를 구할 5개의 수 입력

 

2. 피젯수 n은 1부터 시작한다. 이 수를 입력값 5개로 모두 나눠보며 나누어떨어지는 횟수를 cnt에 저장한다.

cnt가 3 이상이라면 3개 이상의 수의 배수라는 뜻이므로 '적어도 대부분의 배수'가 된다.

이 수를 출력하고 반복문을 끝낸다.

만약 그렇지 않다면 cnt를 0으로 초기화시키고, n을 1 증가시켜 위의 과정을 반복한다.

이렇게 1부터 모든 수들을 하나하나 검사하면 조건을 만족시키는 최소의 수를 어렵지 않게 구할 수 있다.

	while (1) {
		for (int i = 0; i < 5; i++) {
			if (n % num[i] == 0) cnt++;
		}
		//피젯수를 5개의 수로 모두 나눠보면서
		//나누어떨어지는 횟수를 카운트

		if (cnt >= 3) {
			printf("%d", n);
			break;
		}
		//3번 이상 나누어떨어지면 대부분의 배수이므로
		//출력 후 반복문 종료
		else {
			cnt = 0;
			n++;
		}
		//3번 이상 나누어떨어지지 않으면 피젯수 1 증가
		//위의 과정 반복
	}

	return 0;