모항이코딩한다

풀이방법 사용된 것: 수학 BigInteger 2022.06.19 반복문을 통해 곱셈과 나눗셈을 해서, 예전 수학 시간에 배웠던 공식 그대로 계산해주면 된다. 이때 정답의 값이 매우 커질 수 있으므로 꼭 BigInteger를 사용해야 한다. long으로도 부족하다. 코드 Java(2022.06.19) import java.math.BigInteger; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); //입력값 읽어오기 int n = sc.nextInt(); int m = ..

풀이방법 사용된 것: 수학 에라토스테네스의 체 2022.06.19 에라토스테네스의 체를 사용하여 1부터 1,000,000 사이의 모든 소수를 구해놓는다. 구해놓은 데이터를 바탕으로 정답을 출력하면 된다. 코드 Java(2022.06.19) import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner (System.in); int start = sc.nextInt(); int end = sc.nextInt(); //에라토스테네스의 체 수행 boolean[] arr..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.06.17 주어지는 문자열의 길이가 최대 50이므로, 단어를 쪼개는 두 지점을 고르는 경우의 수가 최대 50 곱하기 49 밖에 안 된다. 각 경우마다 쪼개고 뒤집는 과정을 수행하는 데에는 상수시간이 걸린다. 따라서 브루트포스 알고리즘으로 충분히 풀 수 있는 문제이다. 쪼개고 뒤집을 때는 String의 substring 메소드와 StringBuffer의 reverse 메소드를 사용했다. 이렇게 만들어낸 모든 문자열은 TreeSet에 저장하였고, TreeSet의 가장 앞에 있는 문자열을 화면에 출력하여 해결하였다. 코드 Java(2022.06.17) import java.io.BufferedReader; import java.io.IOException; im..

풀이방법 사용된 것: 브루트포스 알고리즘 2022.06.17 문제에 나와있는 것을 그대로 해보면 풀리는 문제이다. 수의 범위가 적기 때문에 브루트포스 식으로 일일이 세어서 풀어도 시간초과 없이 해결된다. 나는 다음과 같이 구현하였다. 먼저, 현재 존재하는 땅 중 가장 낮은 땅보다 더 파내려가면 무조건 손해이며, 가장 높은 땅보다 더 쌓는 것도 무조건 손해이다. 그러므로 정답은 반드시 본래 존재하는 땅의 높이 중 최솟값과 최댓값 사이에 존재한다. 본래 땅 높이의 최솟값부터 최댓값까지에 대하여, 모든 땅을 해당 높이로 평평하게 맞추려면 블럭과 시간이 얼마나 필요한지 직접 세었다. 그 다음, 주머니에 있는 블럭이 모자라지 않았다고 판별될 때만, (걸린 시간, 높이)를 짝지어 TreeMap에 넣었다. Key값을..

풀이방법 사용된 것: 이분 탐색 2022.06.15 랜선 자르기 문제와 동일한 방식으로 풀면 된다. #1654 : 랜선 자르기 풀이방법 사용된 것: 이분 탐색 2022.06.14 1 이상, 갖고 있는 가장 긴 랜선의 길이 이하 중에 정답이 존재한다. 이 범위 내를 이분탐색하면 된다. 범위를 1부터 갖고 있는 가장 긴 랜선보다 1 큰 값까 blowupmomo.tistory.com 특정 높이로 기계를 설정하고 나무를 잘랐을 때 얻을 수 있는 목재의 길이가 M 미만인지 아닌지를 판별하여 이분 탐색을 한다. 코드 Java(2022.06.15) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; im..

풀이방법 사용된 것: 이분 탐색 2022.06.14 1 이상, 갖고 있는 가장 긴 랜선의 길이 이하 중에 정답이 존재한다. 이 정도 범위는 이분 탐색으로 풀었을 때 합리적인 시간 내에 해결된다. 그래서 이분 탐색으로 푸는데, 이때 upper_bound의 방식으로 풀었다. upper_bound에 대한 설명은 아래 게시글에 있다. 초급 7회차 이분탐색 & 분할정복 이분탐색과 분할정복 모두 문제를 쪼개어 해결하는 방식임. 쪼갠다는 것은 무엇인가 문제의 크기가 크면 어렵다. 문제를 작은 부분 문제들로 나누어 풀면 쉬워진다. 문제를 쪼개고, 부분 문제들 blowupmomo.tistory.com upper_bound를 이용하는 이유는 다음과 같다. 이 문제의 상황을 살펴보았을 때, 정답 값 이하의 길이로 랜선을 자..

풀이방법 사용된 것: TreeSet 2022.06.12 TreeSet을 사용한다. A의 모든 요소들을 TreeSet에 넣는다. add()를 사용한다. B의 모든 요소들에 대하여, TreeSet에 포함된 요소라면 TreeSet에서 해당 요소를 지운다. contains()와 remove()를 사용한다. 첫째 줄에 TreeSet의 크기를 출력한다. size()를 사용한다. 둘째 줄에 TreeSet의 모든 요소를 처음부터 출력한다. for(int i: (트리셋 이름)) 을 사용해도 되고, while(!(트리셋 이름).isEmpty()) 반복문 안에서 pollFirst()로 출력해도 된다. 코드 Java(2022.06.13) import java.io.BufferedReader; import java.io.IOE..

풀이방법 사용된 것: 정렬 2022.06.12 각 가격에 대하여, 그 가격에 팔 수 있는 달걀의 개수는 (그 가격 이상을 지불할 의사가 있는 사람의 수) 와 (경래가 가지고 있는 달걀의 총 개수) 중 작은 쪽이다. M명의 사람이 제시한 값 M개에 대하여 각각 위의 방법으로 팔 수 있는 개수를 구한다. 그 결과값이 가장 클 때를 찾고, 결과값이 가장 클 때의 가격이 여러 가지라면 그 중 가장 싼 쪽을 정답으로 택한다. 코드 Java(2022.06.12) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTo..

풀이방법 사용된 것: 정렬 2022.06.12 조건에 맞게 학생 클래스를 정의하고 Comparator를 오버라이드해주면 된다. Comparator를 오버라이드하는 방법은 아래의 게시글에 정리해두었다. 자바에서 내 마음대로 정렬하기: Comparator Overriding 기본 데이터타입이 아닌 객체(Object)를 정렬해야 할 때가 있다. 또한, 자바에서 기본으로 제공해주는 정렬함수로는 수행하기 힘든 복잡한 방식/기준의 정렬이 필요할 때도 있다. 백준 #1931 회의실 blowupmomo.tistory.com 코드 Java(2022.06.12) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

풀이방법 사용된 것: 정렬 2022.06.12 주어진 밧줄들이 견딜 수 있는 하중을 오름차순 정렬한다. 정렬된 리스트의 앞쪽부터(견딜 수 있는 하중이 적은 것부터) 모든 밧줄들에 대하여 (i번째 밧줄이 견딜 수 있는 하중) × (전체 밧줄의 개수 - i) 를 구한다. 이렇게 구한 결과값들 중 가장 큰 것이 정답이다. 코드 Java(2022.06.12) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException{ // ..