깡뇽

DP 유형의 문제를 풀어보자. 라고 다짐하고 문제 봤는데 이게 뭐지...? 했다...ㅎ DP 유형이면 당연히 점화식을 만들줄 알아야 하는데.. 앞으로 꼭 차근차근 맨 처음 경우부터 일단 계산해봐야지!!! 테스트 케이스 개수 만큼의 입력받은 수를 1, 2, 3의 덧셈으로 표현할 때의 표현 가능한 경우의 수를 구하면 된다. 1, 2, 3일 때에는 규칙성이 보이지 않지만 4일 때부터는 규칙을 찾을 수 있다. 1과 2와 3일 때에 경우에 각각 1, 2, 3을 활용하여 다시 경우가 구해지기 때문이다. 9095번 1, 2, 3 더하기 풀이 #솔루션 T = int(input()) def dp(i): if i == 1: return 1 elif i == 2: return 2 elif i == 3: return 4 el..

DP 유형에 속하는 여러 문제들을 풀어보고자 해당 문제를 골랐다. N개의 집을 각각 빨강, 초록, 파랑 색으로 칠하는 비용이 각각 입력된다. 그런데 i번째 집은 i-1과 i+1번째에 해당하는 집들은 같은 색을 선택할 수 없다. 즉, 연속하는 2개의 집은 같은 색일 수 없다는 것이다. 1149번 RGB거리 풀이 [시도1] 맞았습니다!! with 솔루션 N = int(input()) color = [] for _ in range(N): rgb = list(map(int, input().split())) color.append(rgb) for i in range(1,N): color[i][0] = min(color[i-1][1], color[i-1][2]) + color[i][0] color[i][1] = m..

DP 유형에 속하는 여러 문제들을 풀어보고자 해당 문제를 골랐다. 필요하다고 생각하는 N개의 물건에는 각각 무게 W와 가치 V가 있고, 최대 K만큼의 무게까지만 배낭에 담을 수 있다. 최대한 즐거운 여행을 할 수 있도록 물건들의 가치의 최댓값을 찾아야 한다. 12865번 평범한 배낭 풀이 [시도1] 맞았습니다!! with 솔루션 N, K = map(int, input().split()) W = [0] V = [0] dp = [[0]*(K+1) for _ in range(N+1)] for _ in range(1, N+1): w, v = map(int, input().split()) W.append(w) V.append(v) for i in range(1, N+1): for j in range(1, K+1)..

다이나믹 프로그래밍 유형의 문제 중에서 선택했다. 1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 3. 마지막 도착 계단은 반드시 밟아야 한다. 각 계단에 쓰여 있는 점수의 최대합을 구하자. 2579번 계단 오르기 [시도1] 맞았습니다!! with 솔루션 n = int(input()) score = [0] #계단 점수 저장 dp = [0] #각 층까지의 최대 점수 저장 for i in range(n): score.append(int(input())) if n == 1: dp.append(score[1]) elif ..