[백준] 1773번: 폭죽쇼(구현)

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

1773번: 폭죽쇼

코드

import java.util.Scanner;

public class Main {
	
	public static int solve(int N, int C, int[] arr) {
		int count = 0;
		
		for(int i=1; i<=C; i++) {
			for(int j=0; j<arr.length; j++) {
				if(i%arr[j] == 0) {
					count ++;
					break;
				}
			}
		}
		return count;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();
		int C = scan.nextInt();
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++)
			arr[i] = scan.nextInt();
		
		int count = solve(N, C, arr);
		System.out.println(count);
		scan.close();
	}

}

풀이

제한시간은 2초, N의 범위는 10,000 , C의 범위는 2,000,000 이므로 완전탐색을 해도 시간초과가 발생하지 않는다.

따라서 폭죽쇼가 끝나는 시간(C) 까지 완전 탐색을 통해, 각각의 초에 학생들이 폭죽을 터뜨리는 시기가 존재할경우

count 값을 1씩 증가시켜준다.

폭죽이 동시에 터지는 경우 한번만 세아려야 하므로, C까지 완전 탐색을 하면서 arr배열(학생들의 폭죽 주기)에

폭죽이 터지는 주기가 있을경우 break를 통해 다음 초를 탐색한다.

 

 

 

다른 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		String str[] = s.split(" ");
		int n = Integer.parseInt(str[0]);
		int c = Integer.parseInt(str[1]);
		int crr[] = new int[c+1];
		int x=0;
		for(int i=0;i<n;i++){
			x = Integer.parseInt(br.readLine());
			for(int j=x; j<crr.length;j+=x){
				crr[j] = 1;
			}
		}
		int cnt = 0;
		for(int i=0;i<crr.length;i++){
			if(crr[i]==1){
				cnt+=1;
			}
		}
		System.out.println(cnt);

	}
}

시간이 대략 1/3정도 단축된 코드다.

폭죽 주기의 배수를 모두 1로 만들고,

폭죽이 끝나는 시간까지 배열 값이 1인경우 cnt를 1씩 증가시키는 코드.