본문 바로가기

전체 글149

[백준] JAVA 자바 : 골드바흐 파티션 (17103번) 앞에서 배웠던 골드바흐의 추측을 조금 응용한 문제이다. 골드바흐의 추측에서는 두 소수를 출력했다면, 이제 모든 경우의 수를 돌면서 두 소수의 쌍이 나올 때마다 누적을 해서 출력해주면 된다. 실버2 치고는 굉장히 간단한 문제인 듯? import java.io.*; import java.util.Arrays; public class GoldbachPartition_17103 { static final int MAX = 1000000; static boolean[] n_list = new boolean[MAX + 1]; // 소수인지 아닌지를 담을 배열. true = 소수, false = 소수 아님 static StringBuilder sb = new StringBuilder(); public static i.. 2024. 1. 22.
[백준] JAVA 자바 : 8진수 2진수 (1212번) 8진수가 주어졌을 때 2진수로 바꾸는 문제이다. 8진수를 2진수로 바꾸는 방법만 안다면 쉽게 해결할 수 있을 것이다! 8진수를 한 문자씩 끊어서 2진수로 변환한 다음 다 이어붙이면 된다! 사실 직전 문제인 2진수 8진수는 못 풀겠어서… 일단 이거부터 풀었다…ㅜㅜ import java.io.*; public class OctaltoBinary_1212 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); String N = br.readLine();.. 2024. 1. 22.
[백준] JAVA 자바 : 숨바꼭질 6 (17087번) 수빈이의 현재 위치에서 동생들을 모두 찾을 수 있는 D의 최댓값을 구하는 문제이다. 사실 처음에는 되게 막막했는데… 예제 출력들의 공통된 패턴을 찾아본 결과, 동생들의 위치와 수빈이의 현재 위치의 차이(거리)의 최대공약수들 중 가장 작은 값이라는 점이었기에 그걸 구하면 된다. 사실 처음에는 동생들의 위치가 주어지면 그 중 가장 작은 값을 가지고 나머지 거리들과의 최대공약수를 구하려고 min을 선언했는데, 사실 굳이 그럴 필요가 없었다. 가장 작은 값이 아니라도 그냥 아무 거리나 잡고 그 값과 다른 거리들의 최대공약수 중 가장 작은 값을 구하기만 하면 됐다. 어차피 다 공통된 최대공약수를 구하는 것이기 때문에… import java.io.*; import java.util.StringTokenizer; p.. 2024. 1. 22.
[백준] JAVA 자바 : GCD 합 (9613번) 테스트 케이스의 개수가 주어지고, 그만큼 나올 수 있는 모든 두 쌍으로 만든 GCD의 합을 출력하는 문제이다. 사실 호제법과 static 변수만 잘 사용할 수 있다면 큰 어려움 없이 풀 수 있을 듯? 그런데 굳이 static 변수에 저장 안 해도 그냥 main 클래스에 변수 하나 생성해서 거기에 누적합 하면 더 빠를 것 같긴 한데… 난 static으로 했으니 귀찮으니까 이렇게 하자~ㅋㅋ 그런데 최대 수가 100만이기 때문에 int가 아니라 long으로 선언해줘야 한다! 난 처음에 int로 했다가 3번이나 틀렸다… 뒤늦게 깨달음……ㅋㅋㅋㅋ 여하튼 모든 경우의 수에 대해 GCD를 구해서 static long 변수에 계속해서 누적한 후 마지막에 그걸 출력하면 쉽게 해결할 수 있다. import java.io... 2024. 1. 22.
[백준] JAVA 자바 : 조합 0의 개수 (2004번) 조합을 구한 후 뒤에서부터 연속하는 0의 개수를 세는 문제이다. 앞에서 구한 팩토리얼 0의 개수와 비슷한데, 이 경우는 2의 개수도 헤아려 줘야 한다. nCm은 n! / (n-m)!m!이므로 n!의 약수의 개수에서 (n-m)!의 약수 개수와 m!의 약수 개수를 빼주면 된다. 그래서 약수 2의 개수가 5의 개수보다 적어질 수도 있어서 약수 2의 개수와 약수 5의 개수 중 더 적은 수를 반환해주면 된다. import java.io.*; import java.util.StringTokenizer; public class Combination_2004 { public static int stoi(String str) { return Integer.parseInt(str); } public static int f.. 2024. 1. 22.
[백준] JAVA 자바 : 팩토리얼 0의 개수 (1676번) 숫자 N이 주어지면, N!의 맨 뒷자리부터 돌면서 연속된 0의 개수를 구하는 문제이다. 이 알고리즘을 일일이 N마다 팩토리얼을 다 구하려고 하면 오버플로우가 발생한다. N의 최대값이 500인데, 500!은 엄청나게 큰 수이기 때문… 그렇기 때문에 팩토리얼을 구하려면 BigInteger을 쓰거나 해야 하는데 사실 BigInteger은 내 취향이 아니라서 그냥 다른 방법을 고안했다. 처음 고안한 방법은 1부터 N까지 돌면서, 그 수의 약수 중 2, 5, 10이 몇 개 들어가는지 구하는 방법이다. 기본적으로 뒷자리의 0은 약수 중 10이 포함된 개수일 테니 약수 중 10의 개수를 먼저 찾은 다음 5와 2의 개수 중 작은 수를 더해주면 연속된 0의 개수가 나온다. 그런데 여기서 조금 더 생각해보면, 10은 5가.. 2024. 1. 22.
반응형

티스토리툴바