본문 바로가기

수학117

[자바] 백준 22938 - 백발백준하는 명사수 (boj java) 문제 : boj22938 두 점의 거리가 두 반지름의 합보다 작으면 YES, 같거나 크다면 NO를 출력해주면 된다. 두 점 사이의 거리는 이하 그림을 통해알 수 있듯이 피타고라스의 정리를 통해 얻을 수 있고, 그 값이 r1+r2 보다 더 큰지 작은지에 따라 겹치는지 확인 가능하다. 이 때 한 점에서 만나는 경우는 두 점의 거리와 r1+r2가 동일한 경우이다. 수식으로 보면 다음과 같다. 그리고 양변을 제곱해서 2번째 수식으로 풀어야 실수 오차 없이 풀 수 있다. 주의점은 X, Y, R이 모두 최대 10^9의 큰 수이므로, 제곱한 값이 int 범위를 넘어가게 되므로 long으로 연산을 해줘야 한다. 최대 (r1+r2)^2이 (2*10^9)^2 으로 대략 4*10^18인데, long은 대략 9*10^18 까.. 2022. 6. 6.
[자바, 파이썬] 백준 13706 - 제곱근 (boj java) 문제 : boj13706 단순히 제곱근(루트)을 구하는 간단한 문제긴한데, 문제는 정수의 자리수가 최대 800자리나 된다는 점이다. 따라서 큰 수 연산이 필요하다. 파이썬의 경우엔 애초에 무한정 크기의 숫자 표현이 가능하다. 다만 단순히 int(input())**0.5 와 같은 코드로는 불가능한데, 너무 큰 수에대해서는 **0.5가 사용 불가하다고 한다. 찾아보니 math에 isqrt 라는 함수가 있어서 그걸 사용했다. 자바의 경우엔 우선 큰 수의 경우엔 BigInteger로 표현 가능하다. 그리고 BigInteger에 sqrt라는 함수가 있으므로 해당 함수를 사용하면 되는데, 문제는 이게 자바 9에서 추가되었다. 따라서 자바9 이상에서는 간단하다. 자바 8 이하에서 짤려면 비트 연산을 활용해서 직접 제.. 2022. 6. 1.
[자바] 백준 6318 - Box of Bricks (boj java) 문제 : boj6318 입력으로 들어온 n개의 hi의 합이 n으로 나누어 떨어진다고 했으므로, 잘 생각해보면 결국 모두 동일한 높이인 sum(hi)/n 으로 맞춰줘야 한다. 즉, sum(hi)/n 보다 큰 hi들에서 하나씩 빼서 sum(hi)/n 미만의 hi들에 더해줘야 한다. 이 말은 다시 말해, n개의 hi들에 대해 이하의 값을 구하면 된다. 여기서 hi_k는 k번째 hi 값을 의미하고, sum(hi)/n은 n개의 hi값의 합을 n으로 나눈 값이다(나누어 떨어진다는 조건이 있으므로 정수). 말로 설명하면, sum(hi)/n보다 큰 hi값을 초과한 값 부분만 다 더해주면 답이 된다. 코드 : github import java.io.BufferedReader; import java.io.IOExcepti.. 2022. 5. 31.
[자바] 백준 14579 - 덧셈과 곱셈 (boj java) 문제 : boj14579 f(n)를 1부터 n까지를 합친 삼각수라고 하자. 그럼 f(a)*f(a+1)*...*f(b)의 값을 구하는 문제이다. b-a가 최악의 경우라도 999이므로, 일단 f(a)*f(a+1)*...*f(b) 자체는 O(999)로 가능하다. 그럼 f(a)만 빠르게 구할 수 있다면 문제없이 시간 내에 답을 구할 수 있다. 여러 방법이 있을 것인데, 사실 최대 f(1000)까지만 구할 수 있으면 되므로 매번 반복문을 통해 직접 구해줘도 시간내에 통과는 가능하다. 아니면 이하의 등차수열 합 공식을 사용해서 f(n)을 구해도 된다. 이하 코드는 일단 f(a)를 구한 후 거기에 a+1, a+2, ... ,b를 순차적으로 더하면서 곱해줬다. 코드 : github import java.io.Buffe.. 2022. 5. 21.
[자바] 백준 1010 - 다리 놓기 (boj java) 문제 : boj1010 해설은 다음과 같다! 결론은 mCn을 구하면 된다. 코드에서 n = Math.min(n, m-n)은 mCn = mCm-n를 코드로 나타낸 것이다. 일단 연산 도중에 long의 범위를 넘어갈 수 있다. 간단하게는 코드처럼 BigInteger로 처리하면 되고, 사실 n과 m이 그리 크지 않으므로 오차만 적당히 조정해주면 double로 연산해도 통과할 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; import java.math.BigInteger; import java.util.StringTokenizer; public class Main { private void solution() .. 2022. 5. 20.
[자바] 백준 25193 - 곰곰이의 식단 관리 (boj java) 문제 : boj25193 결국 중요한건 음식의 리스트를 '원하는 대로' 조정할 수 있다는 점이다. 그럼 'CCCCA' 와 같은 경우를 생각해보자. 어떻게 해야 연속된 C의 최댓값을 최소화시킬 수 있을까? 'CCACC'처럼 A로 나누면 된다. 'CCCCCAB'와 같은 경우엔 어떨까? 마찬가지로 최대한 C를 그 이외의 음식으로 잘게 나누어야 한다. 'CCACCBC'처럼 나누면 될 것이다. 그렇다면, C의 개수를 C가 아닌 것들의 개수로 나누면 될 것임을 알 수 있다. C가 아닌 것을 A라고 한다면 다음과 같은 식을 계산하면 된다(|X|는 X의 개수를 의미함). +1을 한 이유는 예를들어 1개의 벽으로 나눌 수 있는 구역은 2개이고, 2개의 벽으로는 3개가 된다. 그때문에 +1을 해준 것이다. 올림을 하는 이.. 2022. 5. 16.
[자바] 백준 25191 - 치킨댄스를 추는 곰곰이를 본 임스 (boj java) 문제 : boj25191 만약 콜라, 맥주가 매우 많다하더라도 N보다 더 많이 시킬수는 없다. 또한 N이 충분하더라도 A/2+B ('콜라 2개나 맥주 1개' 이므로 콜라/2의 수와 맥주의 수를 더한다.) 보다 더 많이 시킬수는 없다. 따라서 min(N, A/2+B)를 출력해주면 된다. 코드 : github ... private void solution() throws Exception { int n = nextInt(); int a = nextInt(); int b = nextInt(); int cnt = a/2+b; System.out.println(Math.min(n, cnt)); } ... 2022. 5. 16.
[ABC251] A - Six Characters (AtCoder Beginner Contest 251 in Java) 문제 : abc251_a S를 6/|S| 번 반복출력해주면 된다. 코드 : github ... private void solution() throws Exception { String s = nextLine(); String ans = ""; for (int i = 0; i < 6/s.length(); i++) { ans += s; } System.out.println(ans); } ... 2022. 5. 15.
[자바] 백준 2936 - 채식주의자 (boj java) 문제 : boj2936 우선 이 문제를 풀기위한 가장 기본이 되는 개념부터 알아야 한다. 초등학교나 언젠가 배웠을테지만 까먹었을 수도 있으므로! 삼각형의 넓이는 한 변만 x나 y축에 평행하다면, 평행한 면의 길이 w와, 그와 수직인 높이 h에 대해 w*h/2 로 구할 수 있다. 즉, 아래와 같은 삼각형 3개(검정, 주황, 초록)는 w가 셋 다 동일하고 h도 동일하므로 다른 것 처럼 생겼지만 사실 넓이는 전부 동일하다. 위의 개념만 잘 알고 있다면 문제에서 제시된 삼각형의 어느 지점의 한 점이 주어지더라도 두 구역의 넓이를 동일하게 하는 넓이를 구할 수 있다. 예를들어 아래처럼 주황선으로 나뉜 구역의 넓이는 다음과 같이 w와 h를 잡으면 된다. 이 문제의 경우 입력에 따라 다양한 경우가 존재한다. 따라서 .. 2022. 5. 10.
[ABC250] D - 250-like Number (AtCoder Beginner Contest 250 with Java) 문제 : abc250_d 최대 10^18 까지 표현이 가능해야 한다. 이 때 p n || calc < 0) break; cnt++; } } System.out.println(cnt); } ... 2022. 5. 9.

티스토리툴바