Goyummy

문제 링크 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 n과 m의 수 범위가 굉장히 크기 때문에, 이전에 팩토리얼 0의 개수 문제를 풀 때 썼던 방법을 그대로 쓰면 시간 초과가 났다. 그래서 다른 방법을 찾아보았다. 조합은 ‘n! / (n-m)!*m!‘ 이다. 여기서 생기는 2와 5의 개수를 통해 뒷자리에 생기는 0의 개수를 구해야한다. 조합 공식을 참고해서, ‘n!의 2의 개수 - (n-m)!의 2의 개수 - m!의 2의 개수' 를 이용하여 2의 개수를 구해야한다. 5의 개수도 마찬가지다. coun..

문제 링크 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 숫자는 인덱싱이 안되기 때문에 str(factorial)을 이용해 문자로 만들고 인덱싱이 되게 하였다. 정답 코드 import sys N = int(sys.stdin.readline()) factorial = 1 for i in range(1,N+1): factorial *= i factorial = str(factorial) result = 0 for i in range(len(factorial)-1,-1,-1): if factorial[i] == '0': result ..

문제 링크 https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 정답 코드 import sys N = int(sys.stdin.readline()) result = 1 for i in range(1,N+1): result *= i print(result)

문제 링크 https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 수를 나눌 수 있을 만큼 계속 나누고 나눌 수 없을 때, m에 1을 더한다. 정답 코드 import sys number = int(sys.stdin.readline()) m = 2 while number != 1: if number % m == 0: print(m) number //= m else: m += 1

문제 링크 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 소수를 판별하는 함수는 저번 1929번 문제의 ‘에라토스테네스의 체’ 를 그대로 가져왔다. b = number - a를 하고 에라토스테네스의 체 방식을 사용하여 a와 b가 소수인지 판별하였다. 정답 코드 import sys def isPrime(num): if num==1: return False else: for i in range(2, int(num**0.5)..

문제 링크 잘못 짠 코드 import sys M, N = map(int,sys.stdin.readline().split()) def prime_number(number): if number != 1: for i in range(2,number): if number % i == 0: return False else: return False return True for i in range(M, N+1): if prime_number(i) == True: print(i) 직전의 문제와 비슷해서 비슷하게 풀었는데 시간 초과가 나왔다. 다른 사람들의 질문을 보니 ‘에라토스테네스의 체’를 이용하면 시간을 줄일 수 있다고 한다. num**0.5을 하는 이유는 모든 약수들은 대칭 형태를 가지고 있기 때문이다. ( 8 ..

문제 링크 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net def prime_number(number): if number != 1: for i in range(2,number): if number % i == 0: return False else: return False return True 이 함수를 먼저 작성해서 문제에 적용시켰다. 먼저 1이 아닌 숫자를 1과 자기 자신으로 나누어지면 False를 반환시켜서 한번 거르고, else를 이용하여 1을 걸렀다. 마지막에 return True 를 이용하여 두 조건에..

문제 링크 https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net 처음에 문제를 이해하기 어려워서 몇번씩 문제를 읽었다. 예제 입력의 ‘2 16’을 216으로 생각하고 풀었는데 도저히 예제 결과와 같이 나오지 않았다. 알고 보니 2*(17**1)+16*(17**0)으로 풀어야하는 것이었다. for i in range(m): Ato10 += number[i] * (A**i) 으로 A진수를 10진수로 바꾸었다. 정답 코드 import s..

문제 링크 https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 잘못 짠 코드 import sys N_2 = sys.stdin.readline() N_10 = int(N_2, 2) N_8 = '' while N_10 != 0: N_8 += str(N_10 % 8) N_10 = N_10 // 8 print(N_8[::-1]) 이렇게 짜니 시간 초과가 나왔다. 알고보니 oct()라는 8진수로 바꾸어주는 함수가 있어서 이를 활용했다. 정답 코드 import sys print(oct(int(sys.stdin.readline(), 2))[2:])

문제 링크 https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net int(‘문자’,숫자) 로 해야하기 때문에 N과 B를 문자로 받고 이후에 B를 정수로 바꿔주었다. int(N,B) -> B진수인 N을 10진수로 나타내주세요. 정답 코드 import sys N, B = sys.stdin.readline().split() print(int(N, int(B)))