Devjo의 코딩

패션왕 신해빈 1 초 128 MB 12554 6774 5871 54.772% 문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까? 입력 첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다. 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다. 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다. 모든 문자열..

풀이 끝자리 0의 개수는 5와 2의 곱의 개수로 만들어진다. 하지만 2의 개수와 5의 개수만 세어주면된다. 5!은 1개 10!은 2개 15!은 3개 20!은 4개 25!은 6개다. 이런식으로 n!에 대해 5의 개수를 계산하는 메소드를 만들고 입력한 N, M에 대해 N! M! (N-M)!의 5의 개수를 구한다 N!의 5의 개수에서 나머지 둘을 빼주면 끝자리 0의 개수를 구할 수 있다. 반례 - N=5, M=4 2의 개수가 충분하다고 생각할 수 있지만 n=5 m=4가 입력된다면 각각의 5의 배수는 1개, 0개 이므로 1이라는 결과값을 낸다. 하지만 5! ÷ 4!은 5이며 10이 되지 않는다. 이는 둘에서 발견되는 2의 배수의 개수를 고려하지 않았기 때문이다. 위에서 만들어준 논리와 같은 2의 배수의 개수를 ..

이항 계수 2 1 초 256 MB 33293 12522 9832 38.451% 풀이 팩토리얼을 메소드를 만들고 숫자 데이터를 Double로 받아 연산해도 결과값은 NaN이 나온다. 1000까지 곱하기 때문에 Double의 표현 자리수를 넘어가는데 이를 방지하기 위해 중간중간 곱하기마다 10007로 나누어 숫자 크기를 줄여주어야 한다(모듈러 연산). 파스칼의 삼각형 처배열을 이용한 풀이를 생각했지만 파스칼의 삼각형 풀이보다 효율적이지 못한 것 같다. 이항 계수의 성질과 dp를 이용하면 빠르게 풀이할 수 있다. (N K)=(N-1 K-1) + (N-1 K) N을 1000까지 사용하므로 [1001][1001] 배열을 만들고 dp를 적용한다. K=0일 때와 N=K일 때 dp의 값은 1이다. import java..

이항 계수 1 1 초 256 MB 26624 17107 14770 64.442% 풀이 입력값 N, K에 대하여 이항 계수 (N K)의 값은 N!/K!(N-K)! 이다. 팩토리얼 메소드를 활용한다. import java.util.*; public class Main { static int Fac(int N) { if(N

링 1 초 128 MB 8087 6199 5724 78.637% 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌아간다는 사실을 발견했다. 나머지 링은 첫 번째 링 보다 빠르게 돌아가기도 했고, 느리게 돌아가기도 했다. 이렇게 링을 돌리다 보니 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 도는지 궁금해졌다. 링의 반지름이 주어진다. 이때, 첫 번째 링을 한 바퀴 돌리면, 나머지 링은 몇 바퀴 돌아가는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 링의 개수 N이 주어진다. (3 ≤ N ≤ 100) 다음 줄에는 링의 반지름이 상근이가 바닥에 놓은 순서대로 주..

다리 놓기 0.5 초 (추가 시간 없음) 128 MB 42932 19517 15918 48.028% 문제 재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M) 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의..

팩토리얼 0의 개수 2 초 128 MB 31779 14956 12402 47.796% 문제 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (0 ≤ N ≤ 500) 출력 첫째 줄에 구한 0의 개수를 출력한다. 풀이 1! 2! 3! 4! 의 결과는 뒤에서 0이 나오지 않는다. 5!에서 0이 하나 생긴다 6! 7! 8! 9! 은 0이 하나지만 10!에서 00이 된다. 마찬가지로 15! 20!에서 각각 0이 추가된다. 즉 5의 배수 단위마다 0이 추가된다. 그러나 25!은 5가 두번 들어갔기 때문에 2개가 추가된다 5! 10! 15! 20! 까지 0은 4개지만 25!는 0이 6개인 것이다. 25의 배수 50! 75! 100!에서..

최소공배수 1 초 128 MB 33189 19184 16323 59.471% 문제 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있으며, 최소 공배수는 30이다. 두 자연수 A와 B가 주어졌을 때, A와 B의 최소공배수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 둘째 줄부터 T개의 줄에 걸쳐서 A와 B가 주어진다. (1 ≤ A, B ≤ 45,000) 출력 첫째 줄부터 T개의 줄에 A와 B의 최소공배수를 입력받은 순서대로 한 줄에 하나씩 출력한다. 풀이 두 값을 받아 정렬하고..

최대공약수와 최소공배수 1 초 128 MB 49754 29452 23917 60.817% 문제 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다. 출력 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. 풀이 먼저 두 수를 정렬해 작은 수와 큰 수로 분류하고 작은 수에서 계속 1을 빼며 그 수가 두 수의 약수인지 체크, 큰 수에 계속 1,2,3,...을 곱하며 그 수가 두 수의 배수인지 체크한다 import java.util.*; public class Main { public static ..

약수 2 초 512 MB 31943 15932 13835 50.353% 문제 양수 A가 N의 진짜 약수가 되려면, N이 A의 배수이고, A가 1과 N이 아니어야 한다. 어떤 수 N의 진짜 약수가 모두 주어질 때, N을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되지 않는다. 출력 첫째 줄에 N을 출력한다. N은 항상 32비트 부호있는 정수로 표현할 수 있다. 풀이 1과 N을 제외하고 약수를 나열하면 다음과 같다 가장 작은 약수 ....약수들..... 가장 큰 약수 N은 가장 작은 약수와 가장 큰 약수의 곱과 같..