본문 바로가기

알고리즘/백준61

2798번 문제 : 블랙잭 2798번: 블랙잭 (acmicpc.net) 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 후 알고리즘 생각해 내기가 어려웠다. 혜원이가 도와줘서 계산기 열심히 뚜드려가면서 알고리즘을 짰다 1. 배열 정렬 2. 제일 큰 수를 max로 잡고 그 수 보다 인덱스 -1인 값을 중간값으로 잡는다. 그 수가 500을 넘으면 두 번째 수 잘못 잡은 거니까 continue 500을 넘지 않으면 제일 작은수 (k=0) arr[k]를 더해봐서 500이 넘으면 두 번째값 잘못됐으니까 conti.. 2023. 4. 3.
2775번 문제 : 부녀회장이 될테야 2775번: 부녀회장이 될테야 (acmicpc.net) 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 간단해보였는데 알고리즘을 생각하는게 생각보다 복잡했다 ,,., 어떻게 했냐면 일단 0층의 i층에는 i명이 사니까 0층 인원을 반복문을 돌려서 저장했다. 그다음엔 1층 1호부터 인원을 채웠는데 for(int i=1;i 2023. 4. 2.
2751번 문제 : 수 정렬하기 2 2751번: 수 정렬하기 2 (acmicpc.net) 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 너무 간단해 보인다 ! 배열에 넣고 Arrays.sort이용해 오름차순 정렬하면 될 것 같다 ! 는 시간초과 ㅋㅋ package algorithm; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.Ou.. 2023. 3. 31.
2609번 문제 : 최대공약수와 최소공배수 2609번: 최대공약수와 최소공배수 (acmicpc.net) 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net package algorithm; import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.StringTokenizer; public class Main{ public static void main(String[] .. 2023. 3. 30.
2164번 문제 : 카드 2 2164번: 카드2 (acmicpc.net) 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 1부터 N 까지의 카드 -> List로 생성 0번째를 버림 버리고 나서 제일 위에 있는 거를 제일 끝으로 옮김 size()가 1일 때까지 반복 -> while문으로 그때 남아있는 카드 번호 출력 package algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut.. 2023. 3. 29.
2108번 문제 : 통계학 2108번: 통계학 (acmicpc.net) 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 뭘로 구현해야할까 배열, 해시맵, 리스트를 사용하였댜 ! 여기서 Math 클래스 안의 메소드들을 많이 사용해봤다 ! Math클래스의 메소드 - Math.abs(x) //x의 절대값 - Math.max(x,y) //x랑 y중에 큰 값 - Math.round(x) //x를 소수점 첫째자리에서 반올림 HashMap인터페이스의 새로운 메소드인 getOrDefault(key,value)도 사용해봤다. for(int i : arr){ map... 2023. 3. 29.
1966번 문제 : 프린터 큐 1966번: 프린터 큐 (acmicpc.net) 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 자바에 큐라는 자료구조가 있나 ? 있네 Queue queue = new LinkedList(); //인터페이스이기 때문에 큐 인터페이스를 상속받아 구현한 LinkedList클래스를 사용 근데 이건 큐보다는 해시맵을 이용해서 각 문서의 갯수(정수값key)에 중요도를 value로 해서 넣어주면 될 듯. 중요도는 중복이 된다고 했으니 가능 그런데 HashMap 자체가 입력순서를 유지하는 컬렉션이 아니래 ,.,,,,,,,,,.. 2023. 3. 24.
1929번 문제 : 소수구하기 1929번: 소수 구하기 (acmicpc.net) 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 쉬워보인다. 소수란 ? ) 약수가 1과 자기자신 밖에 없는 수 package algorithm; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; import java.util.. 2023. 3. 22.
1920번 문제 : 수 찾기 1920번: 수 찾기 (acmicpc.net) 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 생각보다 간단해보이지만 시간이 짧다. 시간 단축을 위해 이진탐색으로 풀어야하겠고 조건에 정수의 범위 따지는 거 보니까 자료형도 중요하겠다 mid값은 low+high니까 long형을 써야되겠어 이진탐색이 필요할까 싶어서 그냥 구현해봤는데 역시 시간초과가 나왔따 필요하넹 ㅋ package algorithm; import java.io.BufferedReader; impor.. 2023. 3. 20.
728x90

티스토리툴바