반응형 dynamic programming2 BOJ 2096 : 내려가기 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2096 메모리가 4MB로 매우 작은 상태에서 다이나믹 프로그래밍으로 문제를 풀어야 한다. 아래의 4개의 배열로 문제를 풀 수 있다. int A[4]; /* 작은 값 저장 */ int B[4]; /* 큰 값 저장 */ int C[4]; /* 입력 값 */ int D[4]; /* temp 값 */ N번째 내려가기를 했을 때 얻을 수 있는 최소값은 3가지 경우로 나뉜다. 세 개의 수 중 첫 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수를 선택한 경우. 두 번째 수를 선택한 경우 - 이전 값에서 첫 번째 수/두 번째 수/세 번째 수를 선택한 경우. 세 번째 수를 선택한 경우 - 이전 값에서 두 번째 수/세 번째.. 2021. 6. 26. BOJ 14501, 15486 : 퇴사, 퇴사 2 알고리즘 문제 전체 링크 www.acmicpc.net/problem/14501 www.acmicpc.net/problem/15486 퇴사 1의 경우는 완전 탐색으로 풀 수 있지만, 퇴사 2는 N이 매우 크므로, 다이나믹 프로그래밍, 메모이제이션(memoization)으로 풀어야 한다. DP[i] = i일 전까지의 최대 이익 이라고 정의를 하자. i일에 일을 수행하지 않으면, DP[i + 1] = DP[i]와 기존 memoization의 값 중 큰 값이 된다. i일에 일을 수행한다면, i일 전까지의 최대 이익인 DP[i]와 i일에 받을 보수 P[i]를 더한 값 vs 기존 memoization의 값 중 큰 값. 즉, DP[i + T[i]] = DP[i] + P[i] 와 DP[i + T[i]] 중 큰 값을 선.. 2021. 2. 15. 이전 1 다음 반응형
