Programming/Algorithm
문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 예제 입력 1 10예제 출력 1 2 나의 풀이 이 문제를 풀기 위해서 1부터 순서대로 팩토리얼을 구해보다가 5, 10, 15를 기점으로 0이 하나씩 증가하는 것을 보고 5와 관련이 있구나!라는 생각으로 문제를 풀다가 우연히 단계별 풀이에 소인수분해를 활용이라는 힌트를 보게되어 각각의 수들을 소인수분해를 해보니 0의 개수는 곧 5의 개수 였다. 왜냐하면 2*5가 생길때마다 10으로 0이 뒤에 하나씩 붙게되고 이후에 어떠한 수를 곱하게되더라도 이 0의 개수는 증가하면 증가하지 없어지지는 않았다. 그래서 이..
문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 ..
문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 10,007로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ K ≤ N) 출력 (NK)를 10,007로 나눈 나머지를 출력한다. 예제 입력 1 5 2예제 출력 1 10나의 풀이 원래 이항 계수 1 문제가 조합을 푸는 식을 가지고 푸는 문제이고 이 문제가 2차원 배열을 사용해 dp로 푸는 문제였던것 같다. 나는 이미 1번 문제에서 dp로 풀어서 코드를 복붙하고 10,007로 나누어주니 문제를 풀 수 있었다. 아래 dp를 푸는 그림을 한 번 더 첨부하겠다. 코드 import java.util.Scanner; /** * 11051번 이항 계수 2 */ public class B..
문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N) 출력 (NK)를 출력한다. 예제 입력 1 5 2예제 출력 1 10나의 풀이 파스칼의 삼각형을 생각하고 2차원 배열을 만든 뒤 점화식을 세운 뒤 문제를 풀었다. 아래 식과 그림을 첨부하였다. 코드 import java.util.Scanner; /** * 11050번 이항 계수 1 */ public class Baeckjun11050 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.ne..
문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100) 다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주어진다. 반지름은 1과 1000를 포함하는 사이의 자연수이다. 출..
문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입력 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. ..
문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 예제 입력 1 24 18예제 출력 1 6 72나의 풀이 이 문제는 최대공약수를 먼저 구하고 최대공약수를 이용하여 최소공배수를 구하면 쉽게 풀 수 있다. 최대공약수를 구하는 알고리즘으로는 유클리드 호제법이 있다. 간단히 설명하면 x, y (x > y) 두 개의 수가 있다면 y로 x가 나누어 떨어질때까지 반복으로 구하는 것인데 만약 여기서 나누어 떨어지지 않는다면 x에는 y를 y에는 ..
문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. 예제 입력 1 72예제 출력 1 2 2 2 3 3예제 입력 2 3예제 출력 2 3예제 입력 3 6예제 출력 3 2 3예제 입력 4 2예제 출력 4 2예제 입력 5 9991예제 출력 5 97 103 나의 풀이 처음에는 소수들을 미리 저장해놓고 그 소수들을 가지고 나눠야하나 생각을 했었다. 그래서 소인수분해 알고리즘에 대하여 검색을 해보니 그냥 i값을 2부터 증가시키면서 나누어 나머지가 0이 될때를 기록했다. 생각을 해보니 당연한것이었다. 왜냐하면 3인 소수로 나뉘지 않는다면 어차피 3의 배수들로도 ..
문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 출력 첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다. 예제 입력 1 2 4 2예제 출력 1 8 나의 풀이 첫째 줄에서 받는 진짜 약수의 개수만큼 배열을 할당하고 입력으로 받는 진짜 약수들을 배열에 저장한 후 이 배열을 오름차순으로 정렬을 한 뒤 배열의 맨 처음 숫자와 마지막 숫자..
