백준

문제 모든 자리가 1로된 두 수의 1의 갯수가 주어졌을 때 최소공약수를 구하여라. 풀이 주어진 두 수의 1의 갯수의 최소 공약수가 바로 모든 자리가 1로된 두 수의 최소 공약수의 1의 갯수였다.! 따라서 유클리드 호제법을 사용하여 문제를 풀어주었다. 최소 공약수, gcd() private static long gcd(long a, long b){ if(a % b == 0L) return b; else{ return gcd(b, a%b); } } 유클리드 호제법을 재귀함수로 구현하여 사용했다. StringBuilder sb = new StringBuilder(); long N = gcd(a, b); for(int i=0; i

1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 문제 어떤 수 N이 주어졌을 때 N보다 큰 소수이면서 팰린드롬인 수 중 가장 최소값을 출력하시오. 풀이 에라토스테네스의 체 // 1,000,000이 값으로 들어왔을 때 소수이면서 팰린드롬인 수 중 가장 최소값 1003001 boolean[] A = new boolean[1003002]; for(int i=2; i

1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 문제 소수의 제곱(N ≥ 2)으로 표현할 수 있는 수를 “거의 소수”라고 한다. 구간 A와 B가 주어졌을 때 A이상 B이하의 거의 소수를 구하여라 1 ≤ A ≤ B ≤ $10^{14}$ 풀이 먼저 에라토스테네스의 체를 활용하여 소수를 모두 구한 후 계산하였다. 에라토스테네스의 체 // 100,000,000,000,000 -> (10,000,000)^2 즉 천만의 제곱까지만 구하면 거의 소수를 구할 수 있다. boolean[] X = new boolean[10000001];..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 M이상 M이하의 소수를 모두 출력하시오. 풀이 에라토스테네스의 체를 이용하여 소수를 구했습니다.’ 에라토스테네스의 체 for(int i=2; i= N) break; if(!A[now]) A[now] = true; } } 에라토스테네스의 체는 2~ $\sqrt{N}$까지의 모든 곱을 구하여 구해진다면 해당 숫자를 날려 구간의 소수를 모두 구할 수 있습니다. 출력 StringBuilder sb = new StringBuilder(); for(int i= M > 1 ? M : 2 ; i 1 ?..

문제 회의실의 사용시간 (start, end)가 주어졌을 때 최대한 회의를 많이할 수 있는 횟수를 구하여라 풀이 회의가 종료되는 시간이 짧은 회의를 우선으로 두고 구하였다. 정렬 Arrays.sort(A, new Comparator() { @Override public int compare(int[] o1, int[] o2) { if(o1[1] == o2[1]) return o1[0] - o2[0]; else return o1[1] - o2[1]; } }); 종료시간이 짧은 순서대로 정렬하였다. 종료시간이 같은 경우 시작시간이 짧은 순으로 정렬했다. 종료시간이 같을 경우에 해당 회의가 먼저 선택되면 시작시간이 짧은 회의를 선택하지 못하게 된다. 비교 int answer = 0; int now = 0; f..

1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 수식이 주어졌을 때 괄호를 삽입해 식의 최솟값을 구하여라. 풀이 “-”를 기준으로 자르고 합을 모두 계산한 다음 뺄셈연산을 진행해주는 것이 가장 작은 값이라고 생각했다. “-”를 기준으로 문자열을 자른다. “+”를 기준으로 문자열을 잘라 모든 값을 더해준다. 더한값들을 모두 빼준다. 값 입력 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer ..

11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 동전의 종류가 주어졌을 때 주어진 금액을 만들 수 있는 동전 개수의 최솟값을 구하여라. 풀이 다음의 순서로 최솟값을 구한다. 오름차순 정렬되어있기 때문에 N-1부터 값을 낮추면서 주어진 금액과 같거나 작은 동전을 탐색한다. 만약 동전을 찾았다면 주어진 금액/동전금액을 계산하면 동전의 개수를 구할 수 있다. 그리고 주어진 금액을 나머지로 갱신한다. 이 반복을 주어진 금액이 0원이 될 때 까지 반복..

1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 카드 묶음 2개가 주어졌을 때 이 두개의 묶음을 합쳐 정렬하기 위해서는 카드의 갯수를 더한 만큼 비교를해야 한다. 이 때 작은 묶음들부터 더해나가면서 비교하면 최소값이 된다. 카드 묶음들이 주어졌을 때 비교횟수가 가장 작은 최솟값을 구하시오. 풀이 우선순위 큐를 사용하여 큐에 들어오는 값들을 최솟값 순서대로 사용할 수 있도록 정렬해준다. 큐에서 값을 2개씩 꺼내어 값을 합하고 이 값을 큐에 다시 넣는다. 이 값의 합은 answer 더한다. 큐..