개발자로 살아남기

포도주 시식은 포도주를 첫번째로 마시는 경우, 두번째로 마시는 경우, 마시지 않는 경우로 나누어서 생각하면 해결할 수 있다. 6개의 와인잔이 1000, 900, 2, 1, 800, 700 의 순서로 놓여져 있는 경우 다음과 같이 생각할 수 있다. 순서 1 2 3 4 5 6 첫 번째로 마시는 경우 1000 900 1002 1901 2700 2601 두 번째로 마시는 경우 0 1900 902 1003 2701 3400 마시지 않는 경우 0 1000 1900 1900 1901 2701 3번의 경우에 첫 번째로 마시는 경우는 이전에 마시지 않는 경우에서 자신을 더하는 것이다. -> 1000 + 2 = 1002두 번째로 마시는 경우는 이전에 첫번째로 마시는 경우에 자신을 더하는 것이다. -> 900 + 2 = 9..

일반적으로 다이나믹 프로그래밍을 이용하여 피보나치 함수를 구현하는 방법을 그대로 이용하면된다. 다른점은 0을 출력하는 것과 1을 출력하는 것을 따로 저장하여 다음 값의 호출에 0과 1을 출력하는 경우를 모두 더하여 출력하면 된다. dp[N][0] : N번째 수의 0 출력 횟수dp[N][1] : N번째 수의 1 출력 횟수 i번째 수의 0과 1출력 횟수는 다음과 같다. dp[i][0] = dp[i-2][0] + dp[i-1][0];dp[i][1] = dp[i-2][1] + dp[i-1][1];

숫자 삼각형은 위에서부터 순서대로 아래로 내려가면서 현재 노드까지 최대값을 계산하여 자장하는 다이나믹 프로그래밍으로 해결하면된다. 트리형태를 배열에 저장하면 배열의 상단, 좌상단이 현재의 노드에 접근이 가능한 노드 이므로 이 두개의 값과 현재의 값을 더하여 최대값을 저장한다.