B_log

문제 문제 상황 - 선택에 일종의 무게(가격)이 존재한다. - 선택지가 여러가지이고 선택마다 대소가 바뀌어 최선의 선택을 해야한다. 해결 전략 - DP를 이용해 해결하는데 가격이 최대가 아니라 최소이므로 min을 이용하여 해결한다. 코드 1 2 3 4 5 6 7 8 9 10 n = int(input()) RGB = [[] for _ in range(n+1)] for i in range(1,n+1): r,g,b = map(int, input().split()) RGB[i] = [r,g,b] for i in range(2, n+1): RGB[i][0] = min(RGB[i-1][1], RGB[i-1][2]) + RGB[i][0] # red RGB[i][1] = min(RGB[i-1][0], RGB[i-1][..

문제 문제 상황 - 더하는 순서에 따라 같은 숫자의 조합이여도 다르게 인식된다. - itertools 의 permutation을 하기엔 케이스가 너무 커진다. 해결 전략 - 피보나치의 점화식이 되므로 동적프로그래밍을 이용해 Bottom - up으로 해결한다. 코드 1 2 3 4 5 6 7 8 9 10 11 t = int(input()) # testcase tc = [] def p123(n): dp = [0,1,2,4] for i in range(4,n+1): dp.append(dp[i-1]+dp[i-2]+dp[i-3]) return dp[n] for _ in range(t): tc.append(int(input())) for i in range(t): print(p123(tc[i])) cs 해설 새로 학..

동적 계획법의 첫번째 예제로 조건은 세가지이다. 문제 상황 - 경우의 수가 여러가지이고 그 중 최소가 되는 경우가 무엇인지 찾을 수가 없다. - 모든 경우의 수를 무조건 검색하기에는 연산이 너무 많다. 해결 전략 - 동적계획법을 써야한다는 사실은 알지만 적용 방법이 어려웠다. - 검색을 통해 여러가지 코드를 참고하였고 그 중 Bottom-up 방식을 사용하는 것이 그나마 이해가 되었다. 코드 1 2 3 4 5 6 7 8 9 n = int(input()) # 숫자 입력 dp = [0,0,1,1] # 0과 1은 0번으로, 2와 3은 1번의 연산으로 1 가능 for i in range(4, n+1): dp.append(dp[i-1]+1) if i%2 ==0 : dp[i] = min(dp[i], dp[(i//2..