본문 바로가기
320x100

PS84

[CLASS 4]백준 11053번 - 가장 긴 증가하는 부분 수열 11053번 : 가장 긴 증가하는 부분 수열 DP로 구현하면 된다. 처음에는 이렇게 작성했었다. 내 코드: # dawitblog.tistory.com from sys import stdin input = stdin.readline n = int(input()) cache = [1]*n l = list(map(int,input().split())) m = 1 for i in range(1,n): temp = [] for k in range(i,-1,-1): if l[k] m: m = cache[i] print(m) 이렇게 작성했고 맞았지만 속도가 좀.. 2021. 2. 26.
[CLASS 4]백준 9465번 - 스티커 9465번 : 스티커 이 문제를 풀고 확신한 것이 있다. 난 DP를 못한다. 이 문제를 푸는데 한참 걸렸다. 먼저 DP인줄 알기 전까지 다른 방법으로 뻘짓하느라 시간을 날리고, DP인것을 깨닫고 나서 부터도 구현하는데 한참 걸렸다. DP문제만 모아서 왕창 풀어봐야겠다. 내 코드: from sys import stdin input = stdin.readline for _ in range(int(input())): sticker = [] length = int(input()) sticker.append(list(map(int,input().split()))) sticker.append(list(map(int,input().split()))) cache = [[sticker[0][0],sticker[1][0].. 2021. 2. 24.
[CLASS 4]백준 2407번 - 조합 2407번 : 조합 조합... 그냥 공식으로 풀면 된다. n,m = map(int,input().split()) def fac(n): if n == 1: return n return n * fac(n-1) print(fac(n)//fac(n-m)//fac(m)) 일부러 더 어렵게 만들어 푸는것도 좀 웃긴거 같아서 공식을 적용해서 풀었다. 다른 언어 같으면 int변수에 2의31승 이상 넣으면 에러가 나겠지만 파이썬은 100팩토리얼(158자리 수) 도 순식간에 잘 나오고 계산이 잘 된다. 그래서 더더욱 걱정할 것이 없다. 2021. 2. 24.
[CLASS 4]백준 - 15650번, 15652번, 15654번, 15657번 - N과 M 해당 4문제가 모두 N과 M문제이고, 거의 비슷비슷하다. 4문제모두 DFS와 itertools를 사용한 방법 두가지로 풀었다. 복원 추출,비복원 추출,순서 고려 까지 모두 itertools에 구현되어 있다는 점에 놀랐다. 역시 Python... 15650번 # DFS def dfs(length,number): if length == m: print(*result) return for temp in range(number,n+1): result.append(temp) dfs(length+1,temp+1) result.pop() result = [] n,m = map(int,input().split()) dfs(0,1) from itertools import combinations n,m = map(int,.. 2021. 2. 23.

티스토리툴바