정수론4

• 

  백준 1637 java - 날카로운 눈(이진탐색, 누적합, 정수론/feat.생애첫플레 1솔) 해당 문제는 결국 구선생님의 힘을 빌어서 풀게 되었으나 그래도 나만의 방식으로 풀어냈다. 이진탐색 + 누적합 + 정수론의 조합이기 때문에 좀 까다로웠다. 정수론이라고 치기에 애매하긴 하지만... 생애 첫 플레티넘 문제 1솔을 했다!! 1. 이진탐색(매개변수탐색)은 결국 순서대로 탐색하기 + 단절점 찾기가 핵심이다. 2. 일단 탐색할 값을 뭐로 할 지 정해야하는데 입력값중 압도적으로 큰 21XXXXX이 있어서 탐색값은 1 (C - A) / B + 1 의 누적합이 짝수인 경우에는 무조건 NOTHING일 수밖에 없다 왜냐하면 홀수개인게 하나고 나머지가 짝수이므로 누적합이 짝수인 경우에는 무조건 홀수가 없다는 뜻이기 때문이다. 5. 정답을 출력할 때는 홀수 개가 존재하는 특정 숫자에다가 그 숫자의 갯수를 출력해.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 5. 29.

• 

  백준 2004 - 조합 0의 개수 JAVA 해당 문제는 아이디어가 생각날 듯 말 듯해서 누워서 생각하다가 한 10분 잠들었다가 일어났더니 생각나서 풀어버린 문제이다. 가끔 누워서 아이디어를 떠올리다 보면 풀리는 문제가 있다. 1. nCm = n! / ((n-m)! * m!)이다. 2. 끝자리 0의 갯수는 10이 얼마나 있느냐 = 2 * 5 쌍의 개수 3. 그냥 5의 배수 나열해 보기 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125... 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 3 -> 5의 개수는 결국 특정 n에서의 5로 나눈 몫 + 5^2(25)로 나눈 몫... + 5^n으로 나눈 몫 고로 n! 이 포함하는.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 17.

• 

  백준 3036 - 링 JAVA 해당 문제는 엄청 쉬운 문제였다. 기약분수 -> 최대공약수 구하기 문제로 보면 편하다. 1. 첫 번 째 원을 한바퀴 돌리면 나머지 원도 첫 번째 원의 둘레만큼 돌아야 하는구나 2. 결국 기약분수로 표시하라는 것은 그냥 첫 번째 원 둘레 / 나머지 원 둘레겠구나 3. 기약분수는 최대공약수로 분자,분모를 나누면 되겠구나. 4. 유클리드 호제법으로 최대공약수 메서드 구현해야지! package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Boj_3036 { public static void main(.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 15.

• 

  백준 2981 - 검문 JAVA(feat. koosaga님) 해당문제는 한 15분 고민하다가 과감하게 구글링을 한 문제이다. 결국 유클리드 호제법을 사용하는 문제인데 그 전에 유도식이 존재한다. A와 B를 나눠서 나머지가 같다라는 말을 식으로 표현하자면 A = a*M + spare B = b*M + spare -> A - B = M * (a - b) 가 성립된다결국 M*(a-b)을 구하는 문제에 해당하므로 M*(a-b)의 약수들의 집합이 답이다. A, B, C가 있다면 A와 B의 M*(a-b)값과 B-C의 값인 M*(b-c)의 최대공약수(gcd)를 계속 구하여 그 최대공약수의 약수의 집합을 오름차순으로 나열하면 되는 문제이다. 유클리드 호제법의 경우 위키피디아를 보면 잘 나와 있으므로 참고하시라! https://ko.wikipedia.org/wiki/%EC%9C%.. 알고리즘공부(Algorithm Study)/문제풀이(ProblemSolving) 2022. 4. 14.