Most Muscular Most Muscular

기출 : Flipkart 인터뷰 DP의 핵심 아이디어는 계산한 값을 저장하기, 점화식 세우기 이 두 가지이다 이 문제의 최종 결과는 시작 지점에 따라서 결정이 된다 따라서 각 시작 지점에서 시작하여 모두 끝이 났을 때 그 최댓값을 구하면 된다 점화식을 세울 때 주의점은 항상 현재 좌표를 기준으로 식을 세워야 한다는 것이다 점화식은 다음과 같다 dp[i][j] = board[i][j] + max(leftup, max(left,leftdown)) #include using namespace std; int t, n, m; int board[21][21]; int D[21][21]; // D[x][y] : x,0에서 시작했을 때 y열에서의 최댓값 int main() { ios::sync_with_stdio(0..

다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 해결하는 알고리즘 기법이다 다이나믹 프로그래밍은 소스코드 작성 방식에 따라 Top-Down 방식과 Bottom-Up 방식으로 분류된다 재귀 함수를 이용해 다이나믹 프로그래밍 소스 코드를 작성하는 방법을 Top-Down 방식이라고 하고 반복문을 이용해 소스 코드를 작성하는 방법을 Bottom-Up 방식이라고 한다 다이나믹 프로그래밍에 사용되는 전형적인 방식은 Bottom-Up 방식이다 이 방식에서 사용하는 저장용 배열은 DP 테이블이라고 한다 다이나믹 프로그래밍 문제를 해결하기 위한 첫 단계는 해당 문제가 다이나믹 프로그래밍 문제인지 파악하는 것이다 완전 탐색 방식으로 문제를 해결하다가 부분 문제가 중복이 발생한다면 이는..