WoohyunKing의 개발 성장일지

https://www.acmicpc.net/problem/2096import sysinput = sys.stdin.readlinen = int(input())dp_max = [0]*3dp_min = [0]*3for _ in range(n): a, b, c = map(int,input().split()) temp_max = dp_max[:] temp_min = dp_min[:] for i in range(3): if i == 0: dp_max[i] = a + max(temp_max[0],temp_max[1]) dp_min[i] = a + min(temp_min[0],temp_min[1]) elif i == 1: ..

11659번: 구간 합 구하기 4첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 jwww.acmicpc.netn,m = map(int,input().split())numbers = list(map(int,input().split()))answers = []dp = [0]*(n+1)for i in range(1,n+1): dp[i] = dp[i-1] + numbers[i-1]for _ in range(m): i, j = map(int,input().split()) answers.append(dp[j]-dp[i-1])for answer in..

이번 문제는 연속으로 3칸을 밟을 수 없고 한번에 1칸이나 2칸씩 계단을 오를 수 있다는 가정 하에, 마지막 도착 계단까지 도착하는데 얻을 수 있는 총 점수의 최댓값을 구하는 문제이다. 먼저 이 문제는 완전탐색으로 풀 경우에는 N이 최대 300이기 때문에 2^300 의 경우의 수로 인해 시간초과가 발생하게 된다. 따라서 O(n) 시간복잡도로 풀 수 있는 DP 알고리즘을 사용해야 한다. 처음에 이 문제를 풀이했을 때는 dp 테이블을 1차원 배열로 선언해서 점화식을 도출하려고 했었는데, 1차원으로 선언하게 되면 점화식을 세우고 싶어도 연속한 세 계단을 모두 밟아서는 안 된다는 제약 조건을 점화식에 넣을 방법이 없다.(연속해서 몇 개의 계단을 밟았는지 확인할 수 없음) 따라서 i번째 계단까지 밟았을 때의 총 ..

25421번: 조건에 맞는 정수의 개수 2개의 자릿수를 갖고 첫 번째 자리의 숫자와 두 번째 자리의 숫자의 차이가 2보다 작거나 같은 양의 정수 11, 12, 13, 21, 22, 23, 24, 31, 32, ... , 97, 98, 99가 A에 해당된다. 따라서 정답은 39이다. www.acmicpc.net n = int(input()) data = [1 for x in range(1,10)] for i in range(n-1): temp = [] for j in range(9): value = 0 for k in range(j-2,j+3): if 0

n = int(input()) data = [] dp = [1]*n for i in range(n): data.append(int(input())) for i in range(n): for j in range(i): if data[i] > data[j]: dp[i] = max(dp[i],dp[j]+1) print(n - max(dp)) 이번 문제는 임의의 순서로 세워진 번호를 번호 순서대로 배치하기 위한 최소한의 이동횟수를 구하는 문제이다. 번호를 옮기는 횟수를 최소화하기 위해서는 번호 순서대로 세워져있는 어린이들을 최대한 많이 고정시키고 나머지만 이동시켜야 한다. 즉, 가장 긴 증가하는 부분수열 LIS(Longest Increasing Subsequence)의 길이를 구하고 이를 전체 어린이 수에서 빼..

def unboundedKnapsack(k, arr): # Write your code here row = len(arr) col = k dp = [[0]*(k+1) for _ in range(row+1)] for i in range(1,row+1): dp[i][0] = 1 for i in range(1,row+1): for j in range(1,col+1): if j >= arr[i-1]: dp[i][j] = dp[i-1][j] + dp[i][j-arr[i-1]] else: dp[i][j] = dp[i-1][j] for i in range(col,-1,-1): if dp[row][i] != 0: return i 이번 문제는 주어진 배열(arr)의 원소들을 가지고 만들 수 있는 타겟 값(k)을 초과하지..

def cost(B): # Write your code here length = len(B) dp = [[0]*2 for _ in range(length)] for i in range(1,length): # A[i] == B[i]인 경우 dp[i][0] = max(abs(B[i]-B[i-1])+dp[i-1][0], abs(B[i]-1)+dp[i-1][1]) # A[i] == 1인 경우 dp[i][1] = max(abs(1-B[i-1])+dp[i-1][0], dp[i-1][1] ) return max(dp[length-1]) 이번 문제는 자연수 배열 B가 주어질 때, 이 B로부터 새로운 배열 A를 정의할 때 모든 배열의 원소 A[i]는 1

def maxSubarray(arr): # Write your code here len_arr = len(arr) dp_array = [0]*(len_arr) dp_sequence = [0]*(len_arr) dp_array[0], dp_sequence[0] = arr[0], arr[0] for i in range(1,len_arr): dp_array[i] = max(arr[i], arr[i]+dp_array[i-1]) for i in range(1,len_arr): dp_sequence[i] = max(dp_sequence[i-1], dp_sequence[i-1]+arr[i], arr[i]) return [max(dp_array),dp_sequence[len_arr-1]] 이번 문제는 주어진 배열(ar..

def getWays(n, c): # Write your code here coin_count = len(c) dp = [[0]*(n+1) for _ in range(coin_count+1)] for i in range(1,coin_count+1): dp[i][0] = 1 for i in range(1,coin_count+1): for j in range(1,n+1): coin_value = c[i-1] if coin_value > j : dp[i][j] = dp[i-1][j] else: dp[i][j] = dp[i-1][j] + dp[i][j-coin_value] return dp[coin_count][n] 이번 문제는 주어진 c 배열 안의 값들로 n을 만들 수 있는 경우의 수를 구하는 문제이다. 문제..

n = int(input()) data = list(map(int,input().split())) p_count = len(data) dp = [[0]*(n+1) for _ in range(p_count+1)] for i in range(1,n+1): dp[1][i] = data[0]*i for i in range(2,p_count+1): for j in range(1,n+1): if i > j: dp[i][j] = dp[i-1][j] else: dp[i][j] = min(dp[i-1][j], data[i-1] + dp[i][j-i]) print(dp[p_count][n]) 이번 문제는 P1부터 PN까지 카드가 N개가 포함된 카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 지불해야 하는 금액..