DP

푼 날짜 : 2024.10.25푼 문제 : [1890] / 점프사용한 언어 : python알고리즘 : DP  점화식 :dp[i+num][j] += dp[i][j] (if i + num dp[i][j+num] += dp[i][j] (if j + num  현재 위치에서 이동 가능 숫자(num)만큼 뛰었을 때 범위를 벗어나지 않는 경우 현재 값을 더해준다.   코드 :N = int(input())graph_ = []for _ in range(N): row = list(map(int, input().split())) graph_.append(row)dp = [[0 for _ in range(N)] for _ in range(N)]dp[0][0]=1 # 가장 왼쪽 위 칸에서 출발하므로 시작 1로 초기화..

푼 날짜 : 2024.10.18푼 문제 : [9461] / 파도반 수열사용한 언어 : python알고리즘 : DP  점화식 :dp[i] = dp[i-3]+dp[i-2] 생각보다 쉬웠던 점화식 찾기! P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9  라고 문제에 주어졌기 때문에 확인해보면 3번째 전 숫자와 2번째 전 숫자를 더하면 현재 숫자가 나온다.  1, 1, 1, 2, 2, 3, 4, 5, 7, 91, 1, 1, 2, 2, 3, 4, 5, 7, 91, 1, 1, 2, 2, 3, 4, 5, 7, 91, 1, 1, 2, 2, 3, 4, 5, 7, 9...1, 1, 1, 2, 2, 3, 4, 5, 7, 9  이렇게 !!!   코드 :T = int(input(..

푼 날짜 : 2024.10.12푼 문제 : [2096] / 내려가기사용한 언어 : python알고리즘 : DP  접근 방식 :처음에 일반적인 DP로 풀다가 메모리 초과가 났다.생각해보면 DP는 현재값 계산을 위해 이전 값을 활용하기 때문에 다음 계산 전 현재 값을 이전 값으로 덮어씌웠다.# 덮어쓰기dp[0][0] = dp[1][0]dp[0][1] = dp[1][1]dp[0][2] = dp[1][2]dp2[0][0] = dp2[1][0]dp2[0][1] = dp2[1][1]dp2[0][2] = dp2[1][2] 이렇게 하면 모든 DP 배열을 채우지 않고 단순하게 계산할 수 있다.  코드 :import sysN = int(sys.stdin.readline())dp = [[0, 0, 0], [0, 0, 0]]..

푼 날짜 : 2024.10.08푼 문제 : [14501] / 퇴사사용한 언어 : python알고리즘 : DP  접근 방법 : 1) 상담횟수와 금액 배열을 따로 만들자! 금액이 높다고 출력 X상담을 제일 많이 한 날의 금액을 출력 O 따라서 두 값을 적절히 저장할 배열이 필요하다. 2) 계산이 불가능 한 경우를 먼저 지우자! 오늘부터 상담을 시작했을 때 퇴사 전 끝내지 못할 경우 (i + lst[i][0] > N)예를 들어 8일에 상담이 끝나는데 7일에 2일이 걸리는 상담은 불가능하다. 오늘 기준으로 이전 상담을 완료하지 못한 경우 (j + lst[j][0] > i)예를 들어 오늘이 5일인데 2일에 4일짜리 상담을 했다면 오늘 기준으로 상담이 완료되지 않았으므로 상담 불가.3) 계산 시에는 오늘 날짜를 기..

푼 날짜 : 2024.10.02푼 문제 : [2491] / 수열사용한 언어 : python알고리즘 : DP  점화식 :max_dp[i] = max_dp[i-1]+1 (if lst[i-1] min_dp[i] = min_dp[i-1]+1 (if lst[i-1] >= lst[i]) 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력해야 하므로 dp 배열을 2개로 나누었다. 조건은i) 같거나 커지는 것ii) 같거나 작아지는 것  이므로이전 값과 비교해서 연속적으로 이전 값과 같거나 커질 때, 이전 값과 같거나 작아질 때를 계산했다.이후 각 배열의 max값을 찾아 더 큰 값을 출력하도록 구현했다.  코드 :import sy..

푼 날짜 : 2024.10.01푼 문제 : [2749] / 피보나치 수 3사용한 언어 : python알고리즘 : 분할정복, 거듭제곱, DP  푼 방법 : n의 범위를 잘 확인해야 한다. 값의 범위가 1000000000000000000 까지 가능하므로 메모리 초과가 날 가능성을 대비해야 한다!다행히 출력 시에는 1000000으로 나눈 나머지를 출력한다. 요기서 뽀인트🌟🌟 피사노 주기(Pisano Period)에 대해 알고 계신가요?  전 이 문제를 풀면서 알게 되었답니다. ദ്ദി・ᴗ・)✧  피사노 주기란 ?피보나치 수를 K로 나눈 나머지의 주기를 의미한다!일정 주기가 반복되므로 해당 주기를 사용해 문제를 풀면 된다.  그래서 주기는 어떻게 구하는데 ?mod = 10^k 일 때, k > 2 라면, 주기..

푼 날짜 : 2024.09.21푼 문제 : [11055] / 가장 큰 증가하는 부분 수열사용한 언어 : python알고리즘 : DP  점화식:dp[i] = max(dp[i], dp[j]+lst[i]) (if lst[j]  여기서 뽀인트🌟 는 i번째 반복이 끝날 때 현재 dp[i]와 lst[i]를 비교해서 큰 값을 넣어주는 것!안그러면 lst[i]는 0보다 큰 수 인데 dp[i]에는 0이 들어가 있게 된다. 이렇게 되면 다음 계산에 영향을 준다!!   코드 :import sysN = int(sys.stdin.readline())lst = list(map(int, sys.stdin.readline().split()))dp = [0 for _ in range(N)]dp[0] = lst[0]for i in ..

푼 날짜 : 2024.09.14푼 문제 : [9465] / 스티커사용한 언어 : python알고리즘 : DP  점화식 :dp[0][i] = max(dp[1][i-1]+sticker[0][i], dp[1][i-2]+sticker[0][i]) dp[1][i] = max(dp[0][i-1]+sticker[1][i], dp[0][i-2]+sticker[1][i])  점화식 도출 과정은 다음과 같다.아래와 같은 예시가 있을 때를 기준으로 계산해보겠다. 이는 sticker배열이다.501010020403050701060  dp 배열은 초기값을 이렇게 설정해주었다.5040   30100     초기값을 이렇게 설정한 이유는 다음과 같다.스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수..