정수론17 [자바] 백준 1684 - 같은 나머지 (java) 목차 문제 : boj1684 필요 알고리즘 정수론, 유클리드 호제법 의외로 GCD 문제이다! ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 N이 2인 경우만 생각해보자. 문제에서 입력된 어떠한 정수 2개를 N1, N2라고 하면, R1==R2가 되려면 아래처럼 식이 전개될 것이다. 따라서 N2-N1 즉, 두 수의 차이는 정수인 Q2-Q1과 D의 곱이 된다. 이 때 Q2-Q1이 뭔지는 모르겠지만 아무튼 정수인 D가 가장 크.. 2023. 7. 25. [자바] 백준 7481 - ATM놀이 (java) 문제 : boj7481 필요 알고리즘 개념 정수론, 수학 나머지 연산을 사용해 풀 수 있다. 비둘기집의 원리 현재는 테스트케이스가 너무 빈약해서 의미 없지만, 테스트케이스 추가 시 통과하려면 비둘기집의 원리로 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 a와 b 중 큰 수를 hi, 작은 수를 lo 라고 해보자. 우선 가장 적은 수의 지폐를 만들려면, 가능한 경우의 수 중 hi가 가장 큰 경우를 찾아야 한다. .. 2023. 1. 31. [자바] 백준 2859 - 별 관찰 (java) 문제 : boj2859 필요 알고리즘 개념 수학, 정수론, 브루트포스 수식을 정리해 브루트포스로 모든 경우를 살펴보면서 나누어떨어지는 경우를 찾아야한다. 비둘기집의 원리 좀 더 명확하게 횟수를 지정하고 싶거나, 몇 번 해야 Never인지 따로 판단하지 않으려면 이게 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 시간과 분으로 된 문자열은 처리하기가 상당히 까다롭다. 그러니 우선 정수로 변환하기 위해 입력값을 .. 2023. 1. 30. [자바] 백준 1323 - 숫자 연결하기 (java) 문제 : boj1323 필요 알고리즘 개념 수학, 정수론 나머지 연산의 법칙을 활용하는 수학문제이다. 비둘기집의 원리 불가능한 경우를 알기 위해 비둘기집의 원리를 사용해야 한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 N이 10억까지 가능한데, 이걸 3번만 붙여도 long 으로 표현 가능한 수치를 넘어간다. BigInteger를 사용해 뭔가를 구하게되면 결국 문자열로 처리하는 것이므로 연산 속도가 엄청나게 느려진다. .. 2023. 1. 21. [자바] 백준 4375 - 1 (java) 문제 : boj4375 필요 알고리즘 개념 브루트포스 풀이1의 경우 BigInteger를 사용해 브루트포스로 푼다. 수학, 정수론 풀이2의 경우 나머지 연산의 특성을 사용해 BigInteger를 사용하지 않고 푼다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 2와 5로 나누어 떨어지지 않는다는 조건이 왜 붙었냐면, 소인수분해시 2와 5가 있을 경우 그 중 작은 수 만큼 수의 낮은 자리수에 0이 생겨서 1로 나누어떨어.. 2022. 11. 26. [자바] 백준 1990 - 소수인팰린드롬 (java) 문제 : boj1990 필요 알고리즘 개념 소수 판정, 에라토스테네스의 체 팰린드롬도 판정해야하지만, 그보다 먼저 소수 판정을 할 수 있어야 한다. 에라토스테네스의 체를 알고 있어야 1억 이하의 소수를 효율적으로 구할 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 1. b 이하의 소수를 모두 구한다. 에라토스테네스의 체를 사용해 구해주면 된다. 이 때 sqrt(b) 까지만 확인해주면 된다. (에라토스테네스의 체 혹.. 2022. 11. 10. [자바] 백준 25375 - 아주 간단한 문제 (java) 문제 : boj25375 필요 알고리즘 개념 정수론, 수학 수학적인 추론이 필요한 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 a, b가 최대 10^18 이므로 당연히 x, y를 직접 찾아낼 순 없다. 그렇다면 수학적인 추론이 필요할 것임을 예측할 수 있다. 수학적으로 매우 약하기 때문에 내 경우엔 우선 간단히 생각해낼 수 있는 부분을 생각해봤다. gcd(x,y) = a 라면 당연히 x와 y는 각각 a로 나누어 .. 2022. 10. 19. [자바] 백준 12993 - 이동3 (java) 문제 : boj12993 필요 알고리즘 개념 정수론, 수학 수학적인 사고가 약간 필요하다. 그리디 태그엔 없긴한데 내 경우엔 그리디 개념으로 풀었다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 x, y 중 큰 값이 [3^a, 3^(a+1)) 일 때, k=a 부터 0까지 감소하면서 현재 남은 x와 y중 큰 값에 3^k를 그리디하게 빼준다. 최종적으로 x와 y 모두 0이 되면 1을 출력해주고, 아니면 0을 출력해준다.. 이 .. 2022. 9. 22. [자바] 백준 1214 - 쿨한 물건 구매 (java) 문제 : boj1214 필요 알고리즘 개념 수학, 정수론, 브루트포스 브루트포스로 풀 수 있긴한데, 수학적으로 시간복잡도를 줄여야한다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 이 문제를 풀기전에, 혹시 개념이 잘 떠오르지 않는다면 '백준 14916번 : 거스름돈' 을 먼저 풀어보자. dp로도 풀 수도 있겠지만, 브루트포스로 푸는 경우를 생각해보자. 내 경우엔 이와 비슷한 문제를 풀었던 기억이 나서 거기서 시간을 깎아내.. 2022. 9. 2. [자바] 백준 25487 - 단순한 문제 (Large) (java) 문제 : boj25487 필요 알고리즘 개념 수학 (정수론) 나머지 연산에 대한 수학적 지식이 있어야 풀 수 있다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 당연히 그냥 구하려 하면 O(Tabc)라는 엄청난 수치가 나온다. (대략 6x10^15) mod 연산의 성질을 이용해 풀어야 한다. 의식의 흐름은 다음과 같다. 0. (x mod y) = (y mod z) = (z mod x) 에 대해 1. (x mod y) =y .. 2022. 8. 26. 이전 1 2 다음
