BOJ - [Array - 1773 폭죽쇼] - Bronze II🥉

문제

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

설명

이 문제는 공배수를 이용하는 문제이다 학생들이 폭죽을 쏘는 주기를 끝나는 시간까지의 숫자까지의 범위에서 배수의 갯수를 세야 되는데 여기서 중요한 것은 중복되는 공배수에 경우 따로 빼고 카운트를 해줘야한다는 점이었다. 그래서 나는 원래는 2,000,000의 길이의 int 배열을 만들어 이미 카운트 한 숫자를 기록하여 중복되는 부분을 빼도록 하려고 하였다.

...
int arr[2000000];
int main()
{
	...
	return 0;
}

int 배열로는 저 정도 길이의 배열을 만드는 것은 불가능하다는 판단이 들었다. 그래서 다른 최소공배수를 구하여 중복되는 값을 구하여 카운트된값에서 제외시켜 뺀다는지 다른 대안을 생각해 보았지만 문제 난이도에 맞지 않게 소스가 더 복잡해지게 되었으나 스터디메이트의 도움으로 C언어에서 bool 변수 를 선언할 수 있음을 알게 되었다.

Bool : Boolean의 약자로 int변수와 다르게 기본적으로 변수 하나당 1 바이트의 크기를 가지며 참(True), 거짓(False)로 단 두가지 값만을 가질 수 있다.

단 다른 언어와 달리 C언어 에 경우 별도로 아래와 같이 해더를 선언해 줘야 불리언(boolean)변수를 활용할 수 있다.

...
#include <stdbool.h>

int main()
{
	...
	return 0;
}

불리언 변수가 이문제에 핵심인 이유는 불리언을 배열변수로 만들면 내가 원하는 2,000,000의 길이의 배열을 만드는 것 또한 가능하기 때문이다.

그렇게 되어 내가 생각한 알고리즘을 이 불리언 변수를 배열의 형태로 이용하여 짠 내 풀 소스 코드는 다음과 같다.

#include <stdio.h>
#include <stdbool.h>

bool arr[2000000];
int main() {
    int stu, last_time,stu_time[100],count=0;
    scanf("%d %d",&stu, &last_time);
    for(int i=0; i<stu; i++)
    {
        scanf("%d",&stu_time[i]);
        for(int j=1; j*stu_time[i]<=last_time; j++)
        {
            if(arr[j*stu_time[i]-1] != true)
            {
                arr[j*stu_time[i]-1] = true;
                count++;
            }
        }
    }
    printf("%d",count);
    return 0;
}

위에서 말한대로 학생들의 주기를 입력받자마자 하당 주기 수가 만들수 있는 끝나는 시간(last_time) 이하의 공배수를 모두 불리언 변수인 arr 변수에 모두기록하고 두번째 학생의 주기를 입력받기 시작하고 부터는 반복문을 이용해 i 번째 학생의 주기의 공배수가 겹치는 경우가 있는 지 조사를 하며 카운트를 진행하도록 한다. 그러나 위 소스에서는 코드 작성의 편의상 i 가 1임에도 불구하고 중복검사를 진행하도록 하였다. (한마디로 말해 쓸모없는 과정이 포함된 소스라는 거다…(•_•) )

결과 링크 : http://boj.kr/d5e3841e82d740a08f15b40f8194c019