본문 바로가기

DynamicProgramming32

[백준 2293번] 동전1 n, k = map(int,input().split()) # 1차원 DP 테이블을 사용한 풀이 prices = [0] * n for i in range(n): prices[i] = int(input()) # dp[i] -> i원을 만들 때 가능한 경우의 수 dp = [0 for _ in range(k+1)] # dp[0] -> 0원을 만들 때 가능한 경우의 수, 동전을 사용하지 않는 경우 이므로 1로 초기화 dp[0] = 1 for price in prices: for i in range(price,k+1): dp[i] = dp[i] + dp[i-price] print(dp[k]) # 2차원 DP 테이블를 사용한 풀이(시간초과) # prices = [0] * (n+1) # for i in range(1,.. 2023. 4. 11.
[백준 1520번] 내리막 길 import sys sys.setrecursionlimit(50000000); m, n = map(int,input().split()) area = [list(map(int,input().split())) for _ in range(m)] dp = [[-1]*n for _ in range(m)] nx, ny = [-1,1,0,0], [0,0,-1,1] def dfs(x,y): # 도착 지점에 도달하면 1 리턴 if x == (m-1) and y == (n-1): return 1 # 이미 방문한 길이라면 경우의 수를 구하지 않고 해당 위치에서 출발하는 경우의 수 리턴 if dp[x][y] != -1: return dp[x][y] way_count = 0 for i in range(4): temp_x = x.. 2023. 4. 10.
[백준 2565번] 전깃줄 n = int(input()) data = [] dp = [1]*n for _ in range(n): data.append(list(map(int,input().split()))) data.sort(key=lambda x:x[0]) for i in range(1,n): for j in range(i): if data[i][1] > data[j][1]: dp[i] = max(dp[i], dp[j]+1) print(n-max(dp)) 이번 문제는 A와 B 전봇대 사이에 연결된 전깃줄의 정보와 전깃줄의 개수가 주어졌을 때, 모든 전깃줄이 서로 교차하지 않도록 하기 위해 제거해야 하는 전깃줄의 최소 개수를 구하는 문제이다. 처음에 이 문제를 접했을 때 이전에 풀던 DP 방식(n=1 부터 구하면서 점화식을 찾는 .. 2023. 3. 25.
[백준 14501번] 퇴사 n = int(input()) data = [] for i in range(n): data.append(tuple(map(int,input().split()))) dp = [0] * 1006 for i in range(n-1,-1,-1): time = data[i][0] value = data[i][1] if (i+time) 2023. 3. 22.
[백준 2193번] 이친수 이번 문제는 이전에 풀었던 01타일 문제와 매우 유사한 문제로, 다음과 같은 조건을 만족하는 이친수의 개수를 구하는 문제이다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 이러한 패턴의 문제는 n=1 부터 차근차근 구하면서 점화식을 찾아내는 것이 핵심인데, n=1부터 차례대로 값을 구해본 결과 다음과 같은 점화식을 얻을 수 있었다. dp[1] = 1, d[2] = 1 dp[n] = dp[n-1] + dp[n-2] (n>=3) 이러한 점화식을 도출한 후, DP 테이블에 저장하여 쉽게 풀 수 있었던 DP 문제였다 :) 2023. 3. 22.
[백준 18353번] 병사 배치하기 import sys input = sys.stdin.readline n = int(input()) data = list(map(int,input().split())) dp = [1]*n for i in range(1,n): for j in range(i): if data[i] < data[j]: dp[i] = max(dp[i],dp[j]+1) print(n - max(dp)) 이번 문제는 병사의 수 N과 각 병사의 전투력 정보를 입력받은 뒤, 모든 병사를 내림차 순으로 정렬하되 남아있는 병사의 수가 최대가 되도록 만드는 문제이다. 해당 문제는 이전에 풀이했던 LIS 문제와 상당히 유사한 문제인데, 문제에서 열외시키는 방법으로 수행한다는 말 때문에 쉽게 떠올리지 못한 것 같다. LIS 문제란 특정 조건을 .. 2023. 3. 16.

티스토리툴바