[백준/C & C++] 1773 폭죽쇼

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

1773번: 폭죽쇼

코드 (C)

#include <stdio.h>

int find(int n, int arr[], int t)
{
	for (int i = 0; i < t; i++) if (n % arr[i] == 0) return 1;	
	return 0;
}

int main()
{
	int n, arr[101] = {0,}, check = 0, j = 1;
	long long time;
	scanf("%d %lld", &n, &time);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
		if (arr[i] == 1) check = 1;
	}

	if (check == 1)
	{
		printf("%lld", time);
		return 0;
	}

	int result = time / arr[0];
	for (int i = 1; i < n; i++)
	{
		int count = time / arr[i];
		for (int j = count; j > 0; j--) if (find(j * arr[i], arr, i) == 0) result++;
	}

	printf("%d", result);
	return 0;
}

코드 (C++)

#include <iostream>
using namespace std;

int find(int n, int arr[], int t)
{
	for (int i = 0; i < t; i++) if (n % arr[i] == 0) return 1;
	return 0;
}

int main()
{
	ios::sync_with_stdio(false); // c,c++ 동기화 해제
	cin.tie(NULL); // 입력 분리

	int n, arr[101] = { 0, }, check = 0, j = 1;
	long long time;
	cin >> n >> time;
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		if (arr[i] == 1) check = 1;
	}

	if (check == 1)
	{
		cout << time;
		return 0;
	}

	int result = time / arr[0];
	for (int i = 1; i < n; i++)
	{
		int count = time / arr[i];
		for (int j = count; j > 0; j--) if (find(j * arr[i], arr, i) == 0) result++;
	}
	cout << result;
	return 0;
}

코드설명

반복문을 돌면서 학생들이 폭죽을 터트리는 주기를 입력받아 배열에 저장한다. 이때 입력되는 값 중에 1이 있다면 매 초마다 폭죽이 터지기 때문에 입력받은 시간 자체가 값이 된다. 그렇기 때문에 1이 있다면 check 변수에 1을 저장하고

학생들의 주기 입력이 끝나자마자 if문을 통해 check가 1인지 여부를 확인한다. 1이면 다른 학생들의 주기를 볼 필요도 없으므로 바로 폭죽쇼가 끝나는 시간을 출력하고 프로그램을 끝낸다. 

 

result 변수에 시간 / 첫 번째 학생의 폭죽 주기를 저장한다.

그 후 2번째 학생부터는 반복문을 이용해 경우를 계산한다. count에 폭죽이 터지는 개수를 저장하고, 한 번 반복문을 도는데, 이 반복문에서는 find함수의 값이 0일 경우 결과에 1을 더한다. 

 

find함수는 이전 학생들의 폭죽으로 인해 이미 해당 시간에 폭죽이 터졌는지 여부를 확인하는 함수이다. 

인수로 i 학생이 폭죽이 터트리는 시간, 학생들의 폭죽 주기를 저장한 배열, i(학생 순서)를 받는다. i 이전의 학생들과 i 학생의 주기를 비교하는 반복문을 돈다. 이때 만약 i학생이 폭죽이 터트리는 시간이 이전 학생의 주기의 배수라면 이전 학생의 주기에 따른 폭죽 횟수를 계산할 때 이미 계산된 것이다. (예를 들어 2번째 학생이 폭죽을 터트리는 시간이 6초인데, 첫 번째 학생이 폭죽을 터트리는 주기가 3이라면 6초에 폭죽이 터지는 것은 이미 결과에 반영되어 있다. ) 그렇기 때문에 이미 있는 경우라는 뜻을 담아서 1을 반환한다. 반복문을 돌면서 경우에 해당하지 않는다는 것은 i학생이 폭죽이 터트리는 시간이 처음 등장했다는 뜻이므로 0을 반환한다. 

 

느낀 점

처음에 문제를 틀렸었는데, 그때는 메인함수의 마지막 반복문(==결과를 구하는 배열)을 while로 선언하고 학생들이 폭죽을 터트리는 시간을 다른 방식을 이용해서 구하고 find함수를 사용했다. 틀렸기 때문에 위와 같이 코드를 수정해서 다시 풀었다.