행복한 개구리

T = int(input()) dp = [[1] for i in range(31)] for i in range(1, 31): for j in range(i+1): if j == 0: dp[i][j] == 1 elif j == i: dp[i].append(1) else: dp[i].append(dp[i-1][j-1]+dp[i-1][j]) for _ in range(T): a, b = map(int, input().split()) if a < b: a, b = b, a print(dp[a][b]) 결국 서쪽 다리와 동쪽 다리의 조합을 구하는 문제입니다. 그리고 출처에 다이나믹 프로그래밍이 포함되어 있길래 dp를 이용해보았습니다. dp를 이용하여 파스칼의 삼각형을 만들겁니다. 이항의 0제곱일 때는 이항계수가 ..

from math import factorial N, K = map(int, input().split()) print((factorial(N)//(factorial(K)*factorial(N-K))) % 10007) 이항계수를 구하여 바로 10007로 나누어줘도 정답처리가 됩니다. 하지만 문제 아랫쪽 알고리즘 분류에 다이나믹 프로그래밍이 있으니 dp를 사용해봅시다. N, K = map(int, input().split()) dp = [[0]for i in range(N+2)] dp[1].append(1) for i in range(2, N+2): for j in range(1, i+1): if j == 1: dp[i].append(1) elif j == i: dp[i].append(1) else: dp[..

n, k = map(int, input().split()) obj = [[0, 0]] dp = [[0]*(k+1) for _ in range(n+1)] for i in range(n): obj.append(list(map(int, input().split()))) for i in range(1, n+1): for j in range(1, k+1): wei = obj[i][0] val = obj[i][1] if j < wei: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-wei]+val) print(dp[n][k]) dp는 위 사진과 같은 결과를 갖습니다. 우선 물건들을 저장할 리스트에 0무게의 0가치를 갖는(비어잇는) 요소를 하나 만..

↓ 틀린 코드 더보기 n = int(input()) arr = list(map(int, input().split())) result = -1001 sum = 0 for i in range(n): for j in range(n-i): for k in range(j, j+i+1): sum += arr[k] if sum > result: result = sum sum = 0 print(result) 수열의 합들을 모두 비교하여 그 중 최댓값을 출력하는 방식입니다. 시간초과가 나왔습니다. n = int(input()) arr = list(map(int, input().split())) sum = [arr[0]] for i in range(len(arr)-1): sum.append(max(sum[i] + arr[..

stringA = input().strip().upper() stringB = input().strip().upper() dp = [[0] * (len(stringB)+1) for i in range(len(stringA)+1)] for i in range(1, len(stringA)+1): for j in range(1, len(stringB)+1): if stringB[j-1] == stringA[i-1]: dp[i][j] = dp[i-1][j-1]+1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) print(dp[-1][-1]) 문자열 A와 B가 주어졌을 때, A와 B의 문자들을 일일히 비교하며 문자열의 최대 길이를 dp에 캐싱해줍니다. 따라서 dp는 stringB..

n = int(input()) wire = [] dp = [1] * n for i in range(n): wire.append(list(map(int, input().split()))) wire.sort(key=lambda x: x[0]) for i in range(n): for j in range(i): if wire[j][1] < wire[i][1]: dp[i] = max(dp[i], dp[j] + 1) print(n - max(dp)) 우선 입력받을 때 전봇대의 순서가 정렬되어 입력되는 것이 아니라는 점에 유의해야 합니다. 따라서 정렬을 해야한다는 생각을 가지고 작성했습니다. 전봇대의 개수에 맞게 wire리스트에 추가해주었습니다. wire리스트의 각 요소는 list형식으로 이루어져 있으며 이 것의 ..