본문 바로가기

분류 전체보기

(402)
[백준 11401번] 이항 계수 3 (Python3) import sys input = sys.stdin.readline mod = 1000000007 N,K = map(int,input().split()) def cal(x,n): if n == 1: return x cal2 = cal(x,n//2) if n%2: return cal2*cal2*x %mod else: return cal2*cal2 %mod numer = denom = 1 for i in range(1,K+1): numer = numer*(N+1-i) %mod denom = denom*(i) %mod denom = cal(denom,mod-2) print(numer*denom%mod) 처음에는 "뭐야 너무 단순한 문제 아니야?" 라고 생각했었다. 그러면서도 당연히 무지성 곱셈하는 문제는 아니..
[백준 1208번] 부분수열의 합 2 (Python3) import sys input = sys.stdin.readline from bisect import bisect_left, bisect_right N,S = map(int,input().split()) seq = [*map(int,input().split())] seq1 = seq[:N//2] seq2 = seq[N//2:] sum1 = [] sum2 = [] def SUM(seq,sumlist,x,start): for i in range(start+1,len(seq)): sumlist.append(x+seq[i]) SUM(seq,sumlist,x+seq[i],i) SUM(seq1,sum1,0,-1) SUM(seq2,sum2,0,-1) sum1.append(0) sum2.append(0) sum1.so..
[백준 2143번] 두 배열의 합 (Python3) import sys input = sys.stdin.readline from bisect import bisect_left,bisect_right T = int(input()) n = int(input()) A = [*map(int,input().split())] m = int(input()) B = [*map(int,input().split())] Aa = [] for i in range(n): SUM = 0 for j in range(i,n): SUM += A[j] Aa.append(SUM) Bb = [] for i in range(m): SUM = 0 for j in range(i,m): SUM += B[j] Bb.append(SUM) Bb.sort() cnt = 0 for a in Aa: cnt ..
[백준 1016번] 제곱 ㄴㄴ 수 (Python3) import sys input = sys.stdin.readline from math import sqrt,ceil sieve = [1]*1000002 sieve[0] = sieve[1] = 0 prime = [] for i in range(2,1000002): if sieve[i]==0: continue prime.append(i) if i>1000: continue n = 2 while i*n
[백준 12850번] 본대 산책2 (Python3) import sys input = sys.stdin.readline mod = 1000000007 D = int(input()) graph = [[0]*8 for i in range(8)] graph[0][1] = graph[0][2] = 1 graph[1][0] = graph[1][2] = graph[1][3] = 1 graph[2][0] = graph[2][1] = graph[2][3] = graph[2][4] = 1 graph[3][1] = graph[3][2] = graph[3][4] = graph[3][5] = 1 graph[4][2] = graph[4][3] = graph[4][5] = graph[4][7] = 1 graph[5][3] = graph[5][4] = graph[5][6] = 1 ..
[백준 12849번] 본대 산책 (Python3) import sys input = sys.stdin.readline mod = 1000000007 D = int(input()) graph = [[0]*8 for i in range(8)] graph[0][1] = graph[0][2] = 1 graph[1][0] = graph[1][2] = graph[1][3] = 1 graph[2][0] = graph[2][1] = graph[2][3] = graph[2][4] = 1 graph[3][1] = graph[3][2] = graph[3][4] = graph[3][5] = 1 graph[4][2] = graph[4][3] = graph[4][5] = graph[4][7] = 1 graph[5][3] = graph[5][4] = graph[5][6] = 1 ..
[백준 2568번] 전깃줄 -2 (Python3) import sys input = sys.stdin.readline from bisect import bisect_left N = int(input()) wire = [] parent = {} for i in range(N): wire.append([*map(int,input().split())]) wire.sort() DP = [0] DPi = [-1] for i in range(N): num = wire[i][1] if num > DP[-1]: DP.append(num) DPi.append(i) parent[i] = DPi[-2] else: idx = bisect_left(DP,num) DP[idx] = num DPi[idx] = i parent[i] = DPi[idx-1] check = [1]*N ..
[백준 14003번] 가장 긴 증가하는 부분 수열 5 (Python3) import sys input = sys.stdin.readline from bisect import bisect_left INF = sys.maxsize N = int(input()) seq = [*map(int,input().split())] DP = [-INF] LIS = [""] for num in seq: if num > DP[-1]: DP.append(num) LIS.append(LIS[-1]+" "+str(num)) else: idx = bisect_left(DP,num) DP[idx] = num LIS[idx] = LIS[idx-1]+" "+str(num) print(len(DP)-1) print(LIS[-1].strip()) 처음에 내가 제출하였던 코드는 이러하다. LCS 2번 문제를 풀..