공부공간

https://www.acmicpc.net/problem/11047 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 동전이 무수히 많고, A(i) 번째는 A(i-1) 번째의 배수이므로 그리디가 성립한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public clas..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 해쉬맵에 다 떄려넣고 GET으로 M개만큼 불러오자 출력에 시간이 걸리므로, 모아서 출력하자. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWri..

// Working program using Reader Class import java.io.DataInputStream; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static class Reader { final private int BUFFER_SIZE = 1

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 0의 개수는 1~N까지의 2와 5의 개수중 작은것만큼 생기므로 N까지 탐색하며 개수를 새준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static int a,b; public static void main(String[] args) throws IOException { BufferedReader br = new..

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 현재의 값이 어떤 제곱수보다 커서 빼질 수 있다면, 그 제곱수의 값에 +1을 해주어 항상 최소를 만족한다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BOJ_17626 { public static void main(St..

https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 솔직히 우선순위큐 2개로 풀려했지만 실패했다.. 시간초과가 계속뜨길래 풀이를 참고하니 Treemap으로 간단하게 푸는 풀이가 대세였다.. Treemap에 대한설명은 구글에 잘 되어있는 자료가 많지만 간단하게 key는 오름차순으로 정렬되며 중간 삭제나 lastget , firstkey로 처음과 끝을 가져 올 수 있는 편리한 자료구조이다. Hashmap 저격데이터가 들어있는경우가 많아서 map자료..

https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 6,9는 번갈아 사용할 수있으므로, 9의 개수를 6에 더해준다. 그리고 만약 6이 최대개수를 가진다면, 세트의 수는 홀수인경우 나누기 2 + 1이고 짝수인경우 나누기 2이다. import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader..

https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 길이가 2^N인 사각형에서 1,2,3,4 분면을 결정한다면, 재귀적으로 상황이 반복됨을 알수있다. 즉 좌표의 값은, 1사분면일경우 그대로, 2사분면인경우 y,x-2^(n-1) 3사분면인경우 y-2^(n-1),x 4사분면인경우y-2^(n-1),x-2^(n-1)으로 반복된다. 또한 사분면에 찍히는 순서의 경우 0,0의 기준에서 2^(2*N-2) * ( 사분면의 수 -1 ) 만큼 보정치를 더해..