수학

[BOJ/JAVA] 1198번: 삼각형으로 자르기

1198번: 삼각형으로 자르기https://www.acmicpc.net/problem/1198키워드볼록 다각형이 있고, 여기서 3개의 연속된 점을 선택해서 삼각형을 만든다. 그 다음, 만든 삼각형을 다각형에서 제외한다. 원래 다각형이 N개의 점이 있었다면, 이제 N-1개의 점으로 구성된 볼록 다각형이 된다. 위의 과정은 남은 다각형이 삼각형이 될 때까지 반복한다.볼록 다각형의 점이 시계 방향순으로 주어진다. 마지막에 남은 삼각형은 여러 가지가 있을 수 있다. 이때, 가능한 넓이의 최댓값을 구하는 프로그램을 작성하시오.구현문제에서는 삼각형을 계속 제거해 나갔지만 결국은 볼록 다각형의 3점으로 만들 수 있는 삼각형 넓이의 최댓값과 동일한 문제이다.N개의 점에서 3개를 선택하여 해당 삼각형의 넓이의 최댓값을 ..

[BOJ/JAVA] 1612번: 가지고 노는 1

1612번: 가지고 노는 1동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 이 원숭이는 수를 이리저리 가지고 노는 것을 매우 좋아한다. 그중에서도 1을 가지고 노는 것을 매우매우매우매우매우 좋아한다. 이제 원숭이가 1을 가지고 노는 법을 알아보자. 원숭이는 1만으로 이루어진 수를 매우매우매우매우매우매우매우 좋아한다. 그래서 어떤 자연수 N이 있을 때, N의 배수 중에서 1만으로 이루어진 수가 있을 까 생각하게 되었다.https://www.acmicpc.net/problem/1612키워드N의 배수 중에서 1만으로 이루어진 수중에 가장 작은 수의 자릿수구현countNumberLength입력받은 값의 자릿수를 계산하는 메소드입력받은 정수를 String으로 바꾼다.해당 문자열의 길이를 반환한다.s..

[BOJ/JAVA] 1644번: 소수의 연속합

1644번: 소수의 연속합하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다.https://www.acmicpc.net/problem/1644키워드하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수구현N이하의 소수 구하기에라토스테네스의 체를 이용하여 소수를 구한다.primeList 소수를 저장한다.N이하 소수의 누적합 구하기..

[BOJ/JAVA] 10830번: 행렬 제곱

10830번: 행렬 제곱크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.https://www.acmicpc.net/problem/10830키워드크기가 N*N인 행렬 A가 주어진다.A의 B제곱을 구하는 프로그램구현matrixMultiply두 정방행렬의 곱을 구하는 메소드시간복잡도 O(N^3)정방행렬의 곱은 다음과 같다.[a1a2a3a4]∗[b1b2b3b4]=[a1b1+a2b3a1b2+a2b4a3b1+a4b3a3b2+a4b4]\begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix} * \begin{bmatrix} b_1 & b_2 \\ b_3 &..

[BOJ/JAVA] 2960번: 에라토스테네스의 체

2960번: 에라토스테네스의 체에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.https://www.acmicpc.net/problem/2960키워드2부터 N까지 모든 정수를 적는다.아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다.P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.구현..

[BOJ/JAVA] 23631번: 진심 좌우 반복뛰기

키워드위치 x = 0에서 시작하여, 처음에는 오른쪽으로 Km를 뛴 다음 방향을 바꾼다.방향을 바꿀 때마다 이전에 움직인 거리에 Km만큼 더한 거리를 뛰고, 다시 방향을 바꾼다.정확히 (N - 1)m만 뛸 것구현다음을 정의하자. 전부 뛴다 → 해당 뛰여야할 길이만큼을 전부 뛴다.n전부 뛴 횟수전부 뛸 수 있는 n값을 구한다.low = 0high = 5000(5000)(5000+1)/2 ≥ 10,000,000 이므로 5000을 상한선으로 정했다.n을 매개변수로 하여, 이분 탐색으로 진행한다.숫자가 매우 크므로, java에서는 BigInteger를 활용한다.n번째에서 전부 뛰었을 때 위치는 다음과 같다.이동 횟수좌표1K2-K32K4-2K53K6-4K위 표에서 알 수 있듯이 이동횟수를 보면, 좌표를 알아낼 수 ..

[BOJ/JAVA] 2981번: 검문

https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.TreeSet; public class java_2981..

[BOJ/JAVA] 10166번: 관중석

https://www.acmicpc.net/problem/10166 10166번: 관중석 KOI 공연장의 관중석에는 가운데에 있는 무대를 중심으로 반지름이 자연수인 동심원(중심이 같은 여러 원들) 위에 다음과 같이 좌석들이 배치되어 있다. 반지름이 1인 원 위에는 좌석이 1개, 반지 www.acmicpc.net 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 java_10166 { stat..

[BOJ/JAVA] 2485번: 가로수

https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class java_2485 { static int euclid(int a, int b) { w..

[java] 2225번: 합분해

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class java_2225 { static int N, K; static long cache[][]; static long ..