300 - 수학 1
나머지 - 10430
나의 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
sb.append((a + b) % c + "\n");
sb.append(((a % c) + (b % c)) % c + "\n");
sb.append((a * b) % c + "\n");
sb.append(((a % c) * (b % c)) % c);
System.out.println(sb.toString());
}
}시키는 대로 작성
최대공약수와 최소공배수 - 2609
나의 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
sb.append((a + b) % c + "\n");
sb.append(((a % c) + (b % c)) % c + "\n");
sb.append((a * b) % c + "\n");
sb.append(((a % c) * (b % c)) % c);
System.out.println(sb.toString());
sc.close();
}
}
유클리드 호제법 알고리즘
최소공배수 - 1934
나의 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = a * b;
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
System.out.println(c / a);
}
sc.close();
}
}
위와 동일한 문제
소수 찾기 - 1978
나의 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int cnt = 0;
for (int i = 0; i < n; i++) {
int m = sc.nextInt();
if (m == 1) {
continue;
}
boolean check = true;
for (int j = 2; j <= Math.sqrt(m); j++) {
if (m % j == 0) {
check = false;
}
}
if (check) {
cnt++;
}
}
System.out.println(cnt);
sc.close();
}
}
소수 찾을 때 제곱근 까지만 판별해보면 된다. ex)16이면 4 까지 확인
소수 구하기 - 1929
나의 풀이
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
boolean[] check = new boolean[m + 1];
check[0] = check[1] = true;
for (int i = 2; i <= Math.sqrt(m); i++) {
if (!check[i]) {
for (int j = 2; i * j <= m; j++) {
check[i * j] = true;
}
}
}
for (int i = n; i < m + 1; i++) {
if (!check[i]) {
System.out.println(i);
}
}
sc.close();
}
}
위의 문제와 같아 보이지만 이번에는 에라토스테네스의 체를 이용하여 더 빠르게 구했다. 2의 배수 3의 배수와 같은 배수들을 전부 제거하는 방법
골드바흐의 추측 - 6588
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n = 0;
boolean[] check = new boolean[1000001];
check[0] = check[1] = true;
for (int i = 2; i <= Math.sqrt(1000000); i++) {
if (!check[i]) {
for (int j = 2; j * i <= 1000000; j++) {
check[i * j] = true;
}
}
}
while ((n = Integer.parseInt(br.readLine())) != 0) {
boolean flag = false;
for (int i = 2; i < n + 1; i++) {
int temp = n - i;
if (!check[i] && !check[temp]) {
sb.append(n + " = " + i + " + " + temp + "\n");
flag = true;
break;
}
}
if (!flag) {
sb.append("Goldbach's conjecture is wrong.\n");
}
}
System.out.println(sb.toString());
}
}
에라토스테네스의 체를 최대 범위값으로 한번만 구해놓으면 시간초과에 걸리지 않는다. 참고로 골드바흐의 추측은 10^18승 까지는 참이므로 Goldbach's conjecture is wrong.이 포함된 테케는 존재 하지 않는다고 함.
팩토리얼 - 10872
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println(fac(Integer.parseInt(br.readLine())));
}
public static int fac(int n) {
return n <= 1 ? 1 : fac(n - 1) * n;
}
}
반복문 or 재귀
팩토리얼 0의 개수 - 1676
나의 풀이
import java.util.Scanner;
public class Main {
static int cnt = 0;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println(fac(sc.nextInt()));
sc.close();
}
public static int fac(int n) {
if (n >= 5) {
cnt += n / 5;
return fac(n / 5);
}
return cnt;
}
}
2와 5가 만나면 0이 생김, 12와 15도 마찬가지 따라서 5로 나누어주고 몫을 더해주어 구함. BigInteger로 구하는 방법도 있음
조합 0의 개수 - 2004
나의 풀이
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
long n = Integer.parseInt(input[0]);
long m = Integer.parseInt(input[1]);
long temp5 = fac5(n) - fac5(n - m) - fac5(m);
long temp2 = fac2(n) - fac2(n - m) - fac2(m);
System.out.println(Math.min(temp5, temp2));
}
public static int fac5(long x) {
int cnt = 0;
while (x >= 5) {
cnt += x / 5;
x /= 5;
}
return cnt;
}
public static int fac2(long y) {
int cnt = 0;
while (y >= 2) {
cnt += y / 2;
y /= 2;
}
return cnt;
}
}이전 문제와 비슷한 점은 2와 5가 만나면 0이 생긴다는 것이다.
따라서 수를 2의 n승과 5의 n승으로 바꾸어 보면
n! = (2의 a1승 5의 a2승)
(n-r)! = (2의 b1승 5의 b2승)
r! = (2의 c1승 5의 c2승)
따라서 조합 공식에 의해 2의 a1-b1-c1승 5의 a2-b2-c2으로 바꿀 수 있다.
그러므로 2의 승수와 5의 승수 중 더 적게 나온 값으로 10이 만들어지므로
승수의 최소값을 구하면 된다.
조합 0의 개수 - 2004
위 마지막 문제는 해결 방법을 생각하기가 조금 어려웠던것 같다.
hello world:)