마탁이의 개발 블로그

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 조합의 출력을 10,007로 나누어야 하는 문제이다. 계산과정에서 나온 값들은 dpArray 혹은 dpDictionrary에 저장하는 식으로 진행하면된다. 값들은 모두 10007 나머지 값들을 사용하면 간단히 구할 수 있다. 더보기 # 25, 12 -> 5200300 N, M = map(int, str(input()).split()) dpDict = dict(); dpDict[0] = 1 dpDict[1] = 1 # r! rFact = 1 if M % 10007 in..

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 백준 1676의 팩토리얼 0의 개수를 응용하는 문제라고 생각된다. 2와 5의 개수를 구해야한다. (10을 만들 수 있는 수) 분자의 2나 5의 개수는 증가 시키고, 분모는 개수에서 뺴야한다. 그리고 출력은 2와 5개수 중에서 작은 수를 출력한다. 더보기 # 25, 12 -> 5200300 N, M = map(int, str(input()).split()) cnt5 = 0 cnt2 = 0 num = 2 while True: if(num > N): break ..

https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 조합을 활용할 수 있어야 한다. 머리에 모자하나만 얹어놔도 된다. 각 옷의 type마다 입지 않았을 경우도 있다는 것을 고려하면 해결할 수 있다. 마지막에는 다 벗었을 경우를 결과에서 차감하였다. 더보기 testCase = int(input()) for tc in range(testCase): N = in..

https://www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 간단한 판별 문제이다. 더보기 import sys input = sys.stdin.readline ''' 첫 번째 숫자가 두 번째 숫자의 약수라면 factor 배수라면 multiple 둘 다 아니라면 neither ''' answerList = [ 'factor', 'multiple', 'neither'] while(True): testCase = list(map(int, str(input()).split())) if 0 == testCa..

https://www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 비례식을 활용하면 풀 수 있는 문제이다. 최대공약수를 구하기 위해 유클리드 호제법 또한 사용해야한다. (기약분수로 결과를 출력하기 위해) 더보기 def gcd(a, b): maxVal = a if a >= b else b minVal = a if a < b else b while 0 != minVal: temp = maxVal % minVal maxVal = minVal minVal = temp return maxVal N = i..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 오래전에 2와 5의 약수 개수를 이용해 C로 풀었다. 이번엔 파이썬으로 다른 방식을 활용해 풀었다. C++ 더보기 #include #include #include #include #include #include #include #include #include #include #define MINSIZE 1 #define MAXSIZE 1 using namespace std; int main() { int N; scanf("%d", &N); //10의 개수로 결정됨 //(1,2,5,1..

https://www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net 주어지는 약수에 대해 최소값 * 최대값을 하면 정답이 나온다. 한 가지 의문은 max(), min()을 따로 구하는 것보다 for 한 번에 maxVal = ?, minValue = ? 을 삼항으로 구하는게 빠를줄 알았는데 아니었다. 더보기 N = int(input()) Nlist = list(map(int, str(input()).split())) st = str(Nlist) maxValu..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 실제적으로 DP를 활용할 수 있는 능력이 필요하다. 그 외에는 수학 공식만 알고있다면 풀 수 있다. 더보기 import sys input = sys.stdin.readline T = int(input()) dpDict = {} for tdx in range(T): N, M = list(map(int, str(input()).split())) if(N == M): print(1) else: # r!..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 회의실의 정렬을 어떻게 해야되는지 처음에 이해하지 못 했었다. 처음에는 끝나는 시간 - 시작 시간으로 cost를 구해서 정렬하였다. 하지만, '빨리 끝날 수록 뒤에서 고려해 볼 기회가 많다' 라는 힌트를 구글링을 통해 찾았고, 끝나는 시간이 같으면 시작 시간을 기준으로 정렬하도록 하였다. 더보기 import sys input = sys.stdin.readline # input N = int(input()) startEndList = [] for ndx in range(N): startEnd = list(map(i..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 그리디 알고리즘을 활용할 수 있다면 간단히 해결할 수 있는 문제이다. 현재 도시와 다음 도시들의 cost를 확인하며 loop를 이용해 계산한다. 더보기 N = int(input()) distList = list(map(int, str(input()).split())) costList = list(map(int, str(input()).split())) distIdx = 0 cityI..