문제 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 접근 방법 1. n! / (m-n)! * m! 를 구할때 끝자리 0 의 개수를 출력하는 문제입니다. 2. 그렇다면 소인수 분해를 하고 곱했을때 0이 되는 수인 2와 5에 대해서 따져보면 됩니다. 3. 2와 5중 둘중 작은 수를 구하면 그것이 0의 개수가 됩니다. ex) 2^2 * 5^2 = 100 , 2^3 * 5^2 = 200 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; publ..

문제 15711번: 환상의 짝꿍 환상의 나라 디디랜드에서는 인연의 증표로 끈을 하나씩 가지고 있다. 그들은 지극히 평범한 방법으로 이 끈을 이용하여 어떤 두 사람이 환상의 짝꿍인지 판단하는데, 두 사람의 끈을 서로 이 www.acmicpc.net 접근 방법 1. A+B를 이어붙이고 이 끈을 나누었을때 소수인 두개로 나눌 수 있는지 판단하는것이었습니다. 2. 두 끈을 이어붙였을때 2부터 ~4 * 10^12 승까지 가능하고, 2와 3은 어떻게 나누어도 소수 두개로 이루어질 수 없으므로 NO를 출력합니다. 3. 4이상일때 짝수와 소수로 나누어 질 수 있는데 짝수일 경우 어떻게 나누어도 소수 2개로 나눌 수 있습니다. (골드바흐의 추측) 4. 홀수는 짝수+홀수 이므로 짝수중 제일 작은 소수인 2를 왼쪽 끈으로 ..

문제 16970번: 정수 좌표의 개수 2차원 좌표 평면 위에서 두 점을 골라 선분을 그었을 때, 지나가는 점의 개수가 K개인 선분의 수를 구해보자. 가능한 점의 좌표 (x, y)는 0 ≤ x ≤ N, 0 ≤ y ≤ M 이고, x와 y는 정수이다. 선분의 양 끝 www.acmicpc.net 접근 방법 1. 어떤 점들이 주어졌을때 이 선분의 기울기는 y2-y1/x2-x1 입니다. 예를들어 0,0과 6,3이라는 점이 주어졌을때 이 점을 지나는 점의 갯수는 (0,0), (2,1), (4,2), (6,3) 이렇게 4개가 주어지게 됩니다. 2. 따라서 최대공약수를 사용하여 dx와 dy의 최대공약수를 구하고 1을 더하면(시작점을 포함하기 때문에) 해당 선분이 지나가는 격자점의 총 수를 구할 수 있습니다. 코드 imp..

문제 2247번: 실질적 약수 첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 방법 1. N 이하의 수에서 어떤 수 i를 약수로 가지는 수의 개수는 N/i개 이다. 2. 그러므로 N/i(자신을 포함한 약수의 개수) - 1 * i(값) 으로 구하면 됩니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static StringBuilder sb; private static BufferedReader br; private static StringTokenizer st..

문제 10859번: 뒤집어진 소수 어제 자다가 알람 시계를 떨어뜨렸는지, 08:15분이 51:80분이 되어 있었다. 그때 나는 디지털로 표시된 어떤 숫자는 180도 뒤집혔을 때도 숫자가 될 수 있다는 걸 깨달았다. 소수 18115211이 디지털로 www.acmicpc.net 접근 방법 1. 문제 그대로 N값에 대해서 소수판별을 진행한다. 2. 들어온값에 3,4,7이 있으면 숫자가 아니다. 3. 뒤집어보고 소수인지 체크해본다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static StringBuilder sb; privat..

문제 14232번: 보석 도둑 희대의 도둑 효빈이는 세계 최고의 보석가게 영선상에 잠입할 계획이다. 이 영선상은 최고의 보석가게답게 최고의 보안장치를 두고 있는데, 이 보안장치를 해제하지 않는다면 보석을 여러 개 www.acmicpc.net 접근 방법 1. 1보다 크면서 보석을 제일 많이 가져올 수 있게 소인수분해를 생각했습니다. 2. 2부터 탐색하며 나누어 주면서 보석을 결정해줍니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static StringBuilder sb; private static BufferedRe..

문제 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 방법 1. 스택을 활용하여 들어오는 값이 시작값(s)보다 크면 값을 push 해주고, 팝을하여 해당번호를 출력합니다. 2. 만약 스택에 넣은 값의 제일 최상단이 들어오는 값이랑 들어오는 값이 다르다면 NO를 출력후 리턴합니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.u..

문제 14718번: 용감한 용사 진수 N명의 적 병사가 있다. 적의 각 병사는 힘, 민첩, 지능의 3가지 능력치를 가진다. 용감한 용사 진수도 힘, 민첩, 지능의 3가지 능력치를 가진다. 적의 각 병사에 대해, 적 병사가 가진 힘보다 진수 www.acmicpc.net 접근방법 1. 처음에 힘, 민첩, 지능을 0 0 0부터 시작하려고했지만 시간초과가 발생할 것이라 생각하였습니다. 2. 다시 생각해보니 진수의 스탯을 병사의 스탯을 조합해서 미리 결정해둡니다. 3. 모든 병사를 돌며, 미리 결정한 힘, 민첩, 지능 모두 병사보다 이상인 것의 횟수를 세고 횟수가 K 이상이면 그 조합의 최소값으로 갱신하면 됩니다. 코드 import java.io.BufferedReader; import java.io.InputS..

문제 5883번: 아이폰 9S 사람 9명이 줄을 서있고 각 사람이 원하는 용량의 크기는 2, 7, 3, 7, 7, 3, 7, 5, 7 이다. 용량 3을 원하는 사람을 줄에서 빼버리면, 줄은 2, 7, 7, 7, 7, 5, 7가 되고, 7을 원하는 사람이 4명이 연속된 구간이 www.acmicpc.net 접근방법 1. N이 1000이기 때문에 이중포문을 돌아도 충분히 가능하다고 생각했습니다. O(N^2) 2. 값을 받을때 후보를 set에 넣어서 set이 포함된 숫자는 건너 뛰어서 가장 긴 연속된 값을 찾으려고 생각했습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; i..

문제 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 접근 방법 1. 왼쪽에서 오른쪽으로 가는 배열에서 큰 기둥을 기준으로 값들을 저장. 2. 오른쪽에서 왼쪽으로 가는 배열에서 큰 기둥을 기준으로 값들을 저장 3. 이렇게 두 배열중 작은 값들을 더하게 된다면 그 값이 가장 작은 창고가 됩니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Str..