Most Muscular Most Muscular

기출 : BOJ #1149 현재 상황을 여러 상황으로 쪼갤 수 있고 각 상황은 직전 선택에서 나온다 (확장성) n번째 색으로 0번 색을 고르는 경우의 최솟값을 D[n][0]이라고 하면 다음과 같은 점화식이 나온다 D[n][0] = min(D[n-1][1], D[n-1][2]) + rgbs[n] # d[n][0] : n번째 r 선택하는 경우 # d[n][0] = min(d[n-1][1], d[n-1][2]) + val[n] n = int(input()) rgbs= list() d = [[0 for _ in range(3)] for __ in range(n)] for _ in range(n): rgbs.append(list(map(int,input().split()))) d[0][0], d[0][1], d[..

기출 : BOJ #1912 현재 상황은 현재 숫자를 포함하는 경우, 포함하지 않는 경우로 나뉜다 현재 숫자를 포함하는 경우 최댓값(d[n][1])은 직전 숫자를 포함하는 경우(d[n-1][1] + arr[n])와 포함하지 않는 경우(arr[n])로 나눌 수 있고 현재 숫자를 포함하지 않는 경우 최댓값(d[n][0])은 직전 상황의 최댓값이다 (max(d[n-1]) 이를 구현하면 다음과 같다 # d[n][1] = n번째를 포함했을 경우의 최댓값 # d[n][0] = n 포함 x 최댓값 n = int(input()) arr = list(map(int, input().split())) d = [[0 for _ in range(2)] for i in range(n)] d[0][0] = arr[0] d[0][1]..

기출 : BOJ #1904 직전에 0이 나오는 경우와 1이 나오는 경우로 나눌 수 있다 D[n][m] = n번째 자리에 m이 나오는 경우의 가짓수 D[n][0] = D[n-2][0] + D[n-2][1] D[n][1] = D[n-1][0] + D[n-1][1] 이렇게 문제를 해결해도 되지만 주어진 메모리 조건에 벗어났다 문제에서 원하는 것은 D[n][0] + D[n][1] 이므로 점화식을 새로 정의했다 D[n] = D[n][0] + D[n][1] D[n] = D[n-1] + D[n-2] n = int(input()) # d[n][0] = d[n-2][0] + d[n-2][1] # d[n][1] = d[n-1][0] + d[n-1][1] # d[n] = d[n-1] + d[n-2] d = [0 for _ ..

기출 : BOJ #2579 선택한 계단들에 새로운 계단을 추가할 수 있다 (확장성) 현재 상황을 직전 상황들로 표현할 수 있다 (점화식 작성 가능) D[n][m] = n번째 계단을 선택할 때 연속으로 m개의 계단을 선택한 경우 최댓값 D[n][1] = max(D[n-2]) + score[n] D[n][2] = D[n-1][1] + score[n] 계산할 범위는 3~n까지 이다 # d[n][2] = d[n-1][1] + score[n] # d[n][1] = max(d[n-2]) + score[n] # d[1][1] = score[1] # d[2][1] = score[2] # d[1][2] = 0 # d[2][2] = score[1] + score[2] 걔 n = int(input()) d = [[0 for..

기출 : BOJ #2156 D[n][m] : n번째 포도주에 대해 연속으로 m개 선택한 경우 포도주의 양 D[n][2] = D[n-1][1] + 포도주[i] D[n][1] = D[n-1][0] + 포도주[i] D[n][0] = max(D[n-1]) n = int(input()) val = list() val.append(0) for _ in range(n): val.append(int(input())) d = [[0, 0, 0] for _ in range(n+2)] d[1][0] = val[0] d[1][1] = val[1] d[1][2] = val[1] if n>=2: d[2][0] = val[1] d[2][1] = val[2] d[2][2] = val[1] + val[2] for i in range(..

출처 : BOJ #10844 기존 계단수 뒤에 숫자를 붙여 새로운 계단 수를 만들 수 있다 (확장성) 새로운 계단 수는 이전 계단 수 끝자리가 증가한 케이스와 감소한 케이스로 나눌 수 있는데 이를 점화식으로 표현하면 다음과 같다 D[n][m] : 자리수 n, 마지막 숫자가 m인 수의 개수 D[n][m] = D[n-1][m-1] + D[n-1][m+1] 초기값 D[1][#] : 1 가장 끝 자리수가 0, 9인 경우 1에서 감소하거나 8에서 증가할때 만들어지므로 이를 고려해야 한다 # 기존 계단 수 뒤에 숫자를 붙여 확장 가능 (확장성) # D[n][m] : 자리수 n, 마지막 숫자가 m인 수의 개수 # D[n][m] = D[n-1][m-1] + D[n-1][m+1] # 초기값 D[1][#] = 1 # 반복..

기출 : BOJ #9095 기존 숫자에 값을 더해 가지수를 늘릴 수 있다 (확장성) 그 경우의 수는 다음과 같다 1. 직전에 3이 오는 경우 2. 직전에 2가 오는 경우 3. 직전에 1이 오는 경우 따라서 점화식을 세워 보면 다음과 같다 D[n] = D[n-3] + D[n-2] + D[n-1] 초기값은 D[1], D[2], D[3] = 1, 2, 4 이다 # 기존의 숫자에 값을 더해 가지수를 늘릴 수 있다 (확장성) # D[n] = D[n-3] + D[n-2] + D[n-1] # 초기값 D[1] = 1, D[2] = 2, D[3] = 4 def calc(t): d = [0 for _ in range(11)] d[1], d[2], d[3] = 1, 2, 4 if t>3: for x in range(4,t+..

기출: BOJ #11727 직전에 풀었던 문제와 동일하다 하지만 초기값과 점화식에 변화가 있다 D[n] = D[n-1] + D[n-2]*2 D[1] = 1 D[2] = 3 # 기존 직사각형에 타일 추가를 통해 새로운 직사각형을 만들 수 있다 (확장 가능) # 점화식 정의 # D[n]: 2*n 타일을 채우는 방법의 수 # D[n] = (D[n-1]) + (D[n-2]*2) # 초기값 : D[1] = 1, D[2] = 3 # 계산 범위 : 3~n n = int(input()) if n!=1: d = [0 for _ in range(n+1)] d[1] = 1 d[2] = 3 for x in range(3,n+1): d[x] = d[x-1] + d[x-2]*2 print(d[n]%10007) else: prin..