본문 바로가기

프로그래밍/백준

 (146)
백준 10830 행렬 제곱 - 파이썬 문제. 풀이. 분할정복의 제곱거듭 공식과 행렬의 공식을 합쳐서 풀면 된다. 지수가 짝 수이면 n^(지수/2) * n^(지수/2), 지수가 홀 수 이면 n^(지수/2) * n^(지수/2) * n 이런 방식으로 풀면 된다. 소스코드. import sys def Square(b): if b == 1: return matrix temp = Square(b // 2) if b % 2 == 0: result = matrix_multiple(temp,temp) return result elif b % 2 == 1: result = matrix_multiple(temp,temp) result = matrix_multiple(result, matrix) return result # 행렬 곱 def matrix_multi..
백준 1676 팩토리얼 0의 개수 - 파이썬 문제 풀이. 팩토리얼을 구한 뒤 리스트로 변형시켜서 리스트의 마지막 인덱스부터 0의 갯수를 세린다. 소스코드. import sys from math import factorial n = int(sys.stdin.readline()) fac = factorial(n) fac = list(map(int, str(fac))) result = 0 for i in range(len(fac)-1, 0, -1): if fac[i]==0: result +=1 else: break print(result)
백준 9375 패션왕 신해빈 - 파이썬 문제. 풀이. 우선 입력은 딕셔너리를 사용해서 입력을 받았다. 의상 종류가 A, B, C가 있을때 (A의 갯수 + 1) * (B의 갯수 + 1) * (C의 갯수 + 1) - 1 을 출력하면 된다. 소스코드. import sys tc = int(sys.stdin.readline()) for i in range(tc): n = int(sys.stdin.readline()) dict = {} for j in range(n): c1, c2 = sys.stdin.readline().split() if c2 not in dict: dict[c2] = 1 elif c2 in dict: dict[c2] += 1 result = 1 for d in dict.values(): result *= d+1 print(resul..
백준 1010 다리 놓기 - 파이썬 문제. 풀이. 우선 이 문제는 조합을 구하는 방식으로 풀 수 있다 M개 중에 N개를 골라야하므로 MCN 으로 풀 수 있다 조합의 식은 (M!) / (N!)*((M-N)!) 이다. 소스코드. import sys from math import factorial tc = int(sys.stdin.readline()) for i in range(tc): N, M = map(int, sys.stdin.readline().split()) result = factorial(M) // (factorial(N) * factorial(M-N)) print(result)
백준 3036 링 - 파이썬 풀이. 분수꼴로 바꾸는건 파이썬 라이브러으이 fractions를 이용했다. 단 분모가 1인거는 분모가 표현이 안되니 조건식을 걸어서 기약분수 꼴로 바꾸었다. 소스코드. import sys import fractions N = int(sys.stdin.readline()) ring = list(map(int, sys.stdin.readline().split())) for i in range(1,len(ring)): a = fractions.Fraction(ring[0], ring[i]) a = str(a) if '/' not in a: a += '/1' print(a)
백준 11051 이항 계수2 - 파이썬 문제. 풀이. 메모제이션을 이용하여 미리 팩토리얼의 경우의 수를 구해놓고 풀었다. 소스코드. import sys factorial = [0] * 1002 factorial[0:2] = 1, 1, 2 for i in range(3,len(factorial)): factorial[i] = factorial[i-1] * i N, K = map(int, sys.stdin.readline().split()) result = factorial[N] // (factorial[K] * factorial[N-K]) print(result % 10007)
백준 11050 이항 계수1 - 파이썬 문제. 풀이. 이항 계수의 풀이법은 N! / (K! * (N-K)!) 이다 풀이법만 알면 쉽게 풀 수 있는 문제이다. 소스코드. import sys from math import factorial N, K = map(int, sys.stdin.readline().split()) result = factorial(N) / (factorial(K) * factorial(N-K)) print(int(result))
백준 2579 계단 오르기 - 파이썬 문제. 풀이. 마지막 계단은 무조건 밟아야한다. 즉 마지막 계단 전 계단을 밟았을 경우와 마지막 계단 전 계단을 밟지 않았을 경우가 있다. 각 경우에서 최댓값을 구하여서 소스코드를 작성하면된다. 소스코드. import sys n = int(sys.stdin.readline()) stair = [0] * 301 dp = [0] * 301 for i in range(n): stair[i] = int(sys.stdin.readline()) dp[0] = stair[0] dp[1] = stair[0] + stair[1] dp[2] = max(stair[1] + stair[2], stair[0] + stair[2]) # 점프를 하고 그 다음 계단을 밟았을 경우, 첫 계단을 밟고 점프를 할 경우 중 최댓값 for ..

티스토리툴바