DP

푼 날짜 : 2024.09.13푼 문제 : [1149] / RGB거리사용한 언어 : python알고리즘 : DP  점화식 :dp[i][0] = colors[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = colors[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = colors[i][2] + min(dp[i-1][0], dp[i-1][1])   초기값은 dp[0]을 colors[0]을 넣어주고 시작했다.그리고 dp테이블을 하나씩 채워나가는데, i번째의 0번째 요소를 채우기 위해서는 i-1번째의 0번이 아닌 1번과 2번 중 더 작은 값을 더해서 채워준다. 이렇게 해야 값을 최소로 만들며 더해갈 수 있기 때문이다.     코드 :impor..

푼 날짜 : 2024.08.03푼 문제 : [1932] / 정수 삼각형사용한 언어 : python알고리즘 : DP  점화식:dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+lst[i][j]  *주의)첫 번째 요소에는 dp[i-1][0]만 더할 수 있다.마지막 요소에는 dp[i-1][j]를 더할 수 없다.=> 둘 다 index error 가 발생하므로 두 부분은 따로 작성해주었다.    일단 이렇게 그림을 그려 이해했다.머리로 생각하는 삼각형 구조와 입력값으로 주어지는 배열의 인덱스를 이해하기 위해 둘 다 그림으로 그렸다.   코드로 출력했을 땐,  첨부 이미지처럼 나온다.   코드:import sysN = int(sys.stdin.readline())lst = []for _ in..

푼 날짜 : 2024.07.25푼 문제 : [2579] / 계단오르기사용한 언어 : python  점화식:dp[i] = max(dp[i-2], dp[i-3]+score[i-1])+score[i] dp - 이전 계산 값을 담는 dp 배열score - 계단점수를 담은 배열 푼 방법 : DP처음에 초기값을 잘못 설정해서 한참을 헤맸다  이해하기 위해 쉽게 그림을 그려보면,   i는 현재 값계단을 3연속 밟지 않으면서, 현재 값을 만들기 위해서는 3전칸+1전칸에 더하거나, 2전칸에 더하는 경우가 만들어진다. dp는 초기값을 잘 설정하는게 중요한데, 초기값 설정은 아래 코드에서 확인할 수 있다.   코드 :import sysN = int(sys.stdin.readline())score = []for _ in ra..

푼 날짜 : 2024.07.24푼 문제 : [11727] / 2×n 타일링 2사용한 언어 : python   점화식: dp[i] = dp[i−2]∗2+dp[i−1] (i≥2)  어떻게 구했냐면... 모를 땐 직접 그려보자  점화식 찾기..  (i-1) 에는 너비를 맞추기 위해 블록 하나(=> 2*1타일)씩을 붙일 수 있지만 (i-2) 에는 두 칸을 붙일 수 있으므로 x2를 해준다는 식으로 이해했다. (=> 2는 2*1타일과 2*2타일 두 개를 의미)  예를 들어 현재 주어진 수가 5라면 가로로 5칸을 차지한다.이럴 경우 이전(i-1) 값인 4에는 1을 붙여야 5칸을 만들 수 있다.그 이전(i-2) 값인 3에는 2를 붙여야 5칸을 만들 수 있다.  코드 :import sysN = int(sys.stdin...

푼 날짜 : 2024.07.22푼 문제 : [11726] / 2×n 타일링 1사용한 언어 : python  점화식:dp[i] = dp[i−1]+dp[i−2] (i≥2)  어떻게 구했냐면...     코드 :import sysN = int(sys.stdin.readline())dp = [0 for _ in range(1000+1)]dp[1] = 1dp[2] = 2dp[3] = 3dp[4] = 5for i in range(5, N+1): dp[i] = dp[i-1] + dp[i-2]print(dp[N]%10007)  DP는 마냥 어렵다고 생각했는데 하다보니 너무 재밌다...(?)   [ DP 풀 때 중요한 것 ]1. 점화식을 잘 세우자! 2. 초기값을 잘 설정해주자!