[Java]알고리즘 기초

박진우·2022년 10월 6일
0

1676 팩토리얼 0의 개수

문제

N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500)

출력

첫째 줄에 구한 0의 개수를 출력한다.

import java.util.Scanner;

public class B1676 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int count =0;
		while(N>5) {
			count+=N/5;
			N/=5;
		}
		System.out.println(count);
	}
}

2004 조합 0의 개수

문제

(nm)n \choose m의 끝자리 00의 개수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 nn, mm (0mn2,000,000,0000 \le m \le n \le 2,000,000,000, n0n \ne 0)이 들어온다.

출력

첫째 줄에
(nm)n \choose m의 끝자리 00의 개수를 출력한다.

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

public class B2004 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int c5 = C5(n)-C5(n-m)-C5(m);
		int c2 = C2(n)-C2(n-m)-C2(m);
		System.out.println(Math.min(c5,c2));
	}
	public static int C5(int a) {
		int count = 0;
		while(a>=5) {
			count+=a/5;
			a/=5;
		}
		return count;
	}
	public static int C2(int a) {
		int count = 0;
		while(a>=2) {
			count+=a/2;
			a/=2;
		}
		return count;
	}
}

9613 GCD합

문제

양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 각 테스트 케이스는 수의 개수 n (1 < n ≤ 100)가 주어지고, 다음에는 n개의 수가 주어진다. 입력으로 주어지는 수는 1,000,000을 넘지 않는다.

출력

각 테스트 케이스마다 가능한 모든 쌍의 GCD의 합을 출력한다.

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

public class B9613 {
	public static int GCD(int a,int b) {
		if(b==0) return a;
		else return GCD(b,a%b);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t =   Integer.parseInt(br.readLine());
		for(int i = 0;i<t;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			int arr[] = new int[n];
			for(int j = 0;j<n;j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			long ans = 0;
			for(int z = 0;z<arr.length-1;z++) {
				for(int x = z+1;x<arr.length;x++) {
					ans+=GCD(arr[z],arr[x]);
				}
			}
			System.out.println(ans);
		}
	}
}

17087 숨박꼭질 6

문제

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

출력

가능한 D값의 최댓값을 출력한다.

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

public class B17087 {
	public static int GCD(int a,int b) {
		if(b == 0)return a;
		else return GCD(b,a%b);
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int arr[] = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i = 0;i<N;i++) {
			arr[i] = Math.abs(Integer.parseInt(st.nextToken())-M);
		}
		int a = arr[0];
		for(int i = 1;i<N;i++) {
			a = GCD(a,arr[i]);
		}
		System.out.println(a);
	}
}
profile
개발자를 꿈꾸는 사람입니다

0개의 댓글