Most Muscular Most Muscular

기출 : 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..

기출: BOJ #11726 일단 기존 직사각형에서 타일을 추가하여 새로운 직사각형을 만들 수 있으므로 DP를 생각해야 한다 (확장성) 새로운 직사각형 D[n]을 만드는 경우는 총 두가지 케이스가 있다 1. 세로 타일 추가 (D[n-1]) 2. 가로 타일 추가 (D[n-2]) 따라서 점화식을 세우면 다음과 같다 D[n] = 2*n 직사각형을 채우는 방법의 수 D[n] = D[n-1] + D[n-2] 초기값은 D[1] = 1, D[2] = 2 이고 구해야 할 범위는 3~n이다 # 기존 직사각형에 타일 추가를 통해 새로운 직사각형을 만들 수 있다 (확장 가능) # 점화식 정의 # D[n]: 2*n 타일을 채우는 방법의 수 # D[n] = (D[n-1]) + (D[n-2]) # 초기값 : D[1] = 1, D[..

기출 : BOJ #1463 DP는 다음 조건을 만족할때 사용한다 1. 큰 문제를 작은 문제로 나눌 수 있다 (점화식 정의 가능) 2. 작은 문제에서 구한 답이 큰 문제에서도 사용된다 만약 DP로 해결해야 한다는 생각을 했다면 DP의 문제풀이 순서는 다음과 같다 1. 점화식 정의하기 2. 범위 설정하기(초기값, 계산할 범위) 이 문제에서 점화식은 다음과 같다 D[n] = n을 1로 만드는 최소 연산의 수 D[n] = min(D[n-1]+1, D[n//2]+1, D[n//3]+1) 다음으로 초기값은 D[1]=0, 계산할 범위는 2~n 이다 # 점화식 정의 # D[n] : n일때 1을 만드는 최소 연산 횟수 # D[n] = min(D[n-1], D[n//2], D[n//3]) # D[1] = 0 # D[2] ..

기출 : 삼성전자 SW 역량테스트 원래 DP 문제를 어려워하긴 했지만 특히 애먹었던 문제다 일단 문제는 DFS 방식으로 전수조사하는 코드를 작성해 보았다 void DFS(int day, int value) { for (int i = day;i n) maxval = max(maxval, value); else if (i + t[i] == n) maxval = max(maxval, value + p[i]); else DFS(i+t[i],value+p[i]); } } 이 방식으로도 문제는 잘 풀렸지만 문제 유형이 DP이므로 다시 풀어 보았다 DP풀이의 핵심은 한번 계산한 것을 저장해 놓고 같은 것을 다시 계산하지 않는 것이다 점화식을 세우면 dp[n] = n일날 ..

기출 : IOI 1994년도, 백준 #1932 점화식을 세우면 다음과 같다 dp[i층][j번째 숫자] = board[i][j] + max(leftup, rightup) #include using namespace std; int n; vector board[501]; vector dp[501]; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0;i tmp; board[i].push_back(tmp); dp[i].push_back(tmp); } } for (int i = 0;i < n;i++) { for (int j = 0;j