정수론

알고리즘 문제) BOJ 20159. 동작 그만. 밑장 빼기냐? 링크 : https://www.acmicpc.net/problem/20159문제 요약N개의 카드와 2명의 플레이어N은 짝수개가 주어짐카드를 분배했을 때 카드 윗장에 적힌 수의 합이 더 큰 사람이 이김카드는 분배한 사람부터 받는다.한번만 밑장 빼기를 할 때 얻을 수 있는 최대 카드 합?밑장 빼기 : 윗장이 아닌 밑장을 보여시간 제한2초입력카드 개수 N2≤N≤10만, 짝수카드의 윗장부터 밑장까지 카드의 값 X가 정수로 주어짐1≤X≤1만출력정훈이가 얻을 수 있는 최대 카드 합?접근법밑장빼기 이해가 어려웠던 문제.. ⇒ 잘 못 이해하고 풀어서 틀림;;;;해당 턴에서 밑장을 빼면 밑장에 있는 카드를 해당 턴에 받게 되고, 그만큼 카드가 밀리게 됨 ⇒ ..

알고리즘 문제) BOJ 14476. 최대공약수 하나 빼기  14476번: 최대공약수 하나 빼기첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다.www.acmicpc.net문제 요약N개의 정수 중 임의의 수 K를 뺐을 때, 나머지 N-1의 최대공약수가 가장 커지는 것을 찾는 프로그램 찾기이때 최대공약수는 K의 약수면 X시간 제한2입력정수의 개수 N(4≤N≤1,000,000)N개의 수가 주어짐(20억 이하 자연수)출력정수 하나를 빼서 만들 수 있는 가장 큰 최대공약수와 수 출력정답이 없다면 -1 출력접근법8 12 24 36 488 = 1 2 4 88 12 20 32 36숫자 K 하나하나 빼가..

알고리즘 문제) BOJ 15711. 환상의 짝꿍   15711번: 환상의 짝꿍환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이www.acmicpc.net문제 요약끈을 이어붙이고 소수인 끈으로 정확히 나눌 수 있다면 환상의 짝꿍환상의 짝꿍인지 판단하기시간 제한1초입력테스트 케이스 T(1≤T≤500)끈의 길이 A, B (1≤A,B≤2조..)출력YES 또는 NO 출력접근법골드바흐의 추측 : 2보다 큰 모든 짝수는 두 소수의 합으로 표현 가능하다.3 4 ⇒ 7 : 1 6 / 2 5 / 3 43 5 ⇒ 8 : 1 7 / 2 6 / 3 5 / 4 4약수 구하기 : $\sqrt{10..

알고리즘 문제) BOJ 2004. 조합 0의 개수  2004번: 조합 0의 개수첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다.www.acmicpc.net문제 요약nCr 끝짜리 0의 개수 출력시간 제한2초입력n, m(0≤m≤n≤2*10^9, n≠0)출력nCr 끝짜리 0의 개수 출력접근법0의 개수를 구한다…1000000000의 약수 생각해보기..10의 소인수는 2와 5이다.즉 끝자리 0이 되려면 nCr을 소인수했을때 2, 5가 최소 하나씩 존재해야함0의 갯수가 1개→최대 9개까지 등장할때2와 5의 개수가 각 1개에서 → 9개로 증가…!!!!즉, 이 쌍의 개수가 몇 개인지 찾아야함~!2, 2*2….. 으로 나누면서 2의 개수 구하..

알고리즘 문제) BOJ 6219. 소수의 자격  6219번: 소수의 자격세 정수 A, B, D가 주어진다.www.acmicpc.net문제 요약A..B에서 숫자 D를 포함하는 소수의 개수자릿값에 D가 몇 개 등장????시간 제한2초입력A B D1 ≤ A ≤ B ≤ 4백만B ≤ A + 2백만출력범위 내에서 숫자 D를 포함하는 소수의 개수?접근법그냥 1부터,,,4백만까지 에라토스테네스체 사용해서 소수 판별 미리 기록 하고범위 내에서 자릿값 체크하면서 D가 등장하는 횟수 카운트 하기…!!!!D가 등장하는 소수 개수 카운트 하는거야,,, 문제 잘 읽기,,,코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRead..

알고리즘 문제) BOJ9417. 최대 GCD  9417번: 최대 GCD첫째 줄에 테스트 케이스의 개수 N (1 www.acmicpc.net문제 요약정수 M개가 주어질 때 모든 두 수의 쌍 중 가장 큰 최대공약수 찾기시간 제한1초입력테스트 케이스 N(1테스트 케이스별 양의 정수 M개 주어짐) (1-2^31 ~ 2^31-1출력케이스별 입력으로 주어진 모든 두 수의 쌍의 최대공약수 중 가장 큰 값?접근법7 5 → 5 2 → 3 2 → 2 1125 15 → 110 15 → 95 15 → 80 15 → 65 15 → 50 15 → 35 15 → 20 15 → 15 5 → 10 5125 25 → 100 25 → 75 25 → 50 252개의 쌍을 구하며 모듈려 연산으로 공약수 구하고 최댓값 갱코드import jav..

알고리즘 문제) BOJ 15736. 청기 백기   15736번: 청기 백기예제 입력 1의 경우 1, 2, 3번 깃발이 존재하고, 3명의 선수가 참가한다. 첫 번째 선수는 1의 배수의 번호를 가진 깃발을 뒤집는다. 초기에 청색이였던 깃발은 첫 번째 선수에 의해 모두 백기로 된www.acmicpc.net문제 요약출전할 선수 N명N개의 깃발이 청색이 위, 백색이 아래첫 선수 → N개의 깃발 중 1의 배수 뒤집기두 번쨰 선수 → 2의 배수 뒤집기i 번째 선수 → i배수 뒤집기마지막 선수가 뒤집으면 끝백색이 위로 놓여있는 수 몇 개?시간 제한1초입력학생 수이자 깃발의 수N(20억)출력백색 수?접근법N=1012345678910oooooooooo o o o o o  o  o  o    o   o      o    o..

알고리즘 문제) BOJ14232. 보석 도둑  14232번: 보석 도둑희대의 도둑 효빈이는 세계 최고의 보석가게 영선상에 잠입할 계획이다. 이 영선상은 최고의 보석가게답게 최고의 보안장치를 두고 있는데, 이 보안장치를 해제하지 않는다면 보석을 여러 개www.acmicpc.net문제 요약한번에 K라는 무게만큼의 보석을 가져올 때, 보석의 최대 개수 구하기무게는 가져가는 보석들의 곱만큼 늘어난다.보석은 무한개 존재!!!시간 제한2초입력들 수 있는 무게 k (2≤k출력훔쳐올 보석 개수 출력보석들의 무게를 오름차순 출력접근법K만큼의 무게만큼 가벼와야 하므로 가져오는 보석들의 무게 abc.. 가 K가 되어야함이때 가장 많은 개수를 가져와야 하니까, 소인수분해를 해서 인수들의 무게를 갖는 보석을 가져온다..!!?숫..

정수론 정리 소수 판정완전 탐색으로 접근1️⃣ 1부터 n까지 나누어 떨어지는 경우가 2개면 소수(1과 자기자신), 그렇지 않으면 소수가 아님을 판단import java.util.Scanner;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int cnt = 0; for (int i = 1; i  2️⃣ 1부터 n/2까지로 범위를 줄여 탐색해도 된다. 그 이유는 n/2보다 큰 수는 뭘 곱해도 n이 될 수 없기 때문이다.import java.util.Scanner;public class M..