땅따먹기

https://school.programmers.co.kr/learn/courses/30/lessons/12913

프로그래머스

 

 

이렇게 2차원 배열을 순회하면서

max 값을 받아오고 path 에 기억해뒀다가

다음 순회 때 그 위치의 값을 0으로 셋팅 후 차례로 더하면 잘 될 줄 알았다

DP 를 써서 풀어야함

설명

1. 이중 루프를 통해 각 위치 계산:
   • 첫 번째 행을 제외한 각 행을 순회합니다.
   • 각 열에 대해 이전 행의 같은 열을 제외한 최대값을 현재 위치의 값에 더합니다.
2. 최종 결과 계산:
   • 마지막 행에서 최대값을 찾아 반환합니다.

 

왜 기존 방식이 문제였는지?

기존 방식에서는 다음 행의 동일한 열 값을 0으로 설정하여, 그 열을 선택하지 못하도록 했습니다. 하지만 이 방식은 현재 선택이 이후 선택에 미치는 영향을 충분히 고려하지 못합니다. 예를 들어, 중간에 잘못된 선택을 할 경우, 이후의 선택이 최적해에서 멀어지게 됩니다.

반면에 DP를 사용한 방식은 각 위치에서 가능한 모든 최적의 경로를 고려하여 누적된 값을 사용하므로, 최적의 점수를 보장합니다.

정리

• 기존 방식: 각 행에서 최대값을 선택하고, 이후 선택에 영향을 주어 최적해를 보장하지 못함.
• DP 방식: 각 위치에서 최적의 값을 누적하여 최종적으로 최적의 해를 보장.

따라서, DP를 사용한 방식이 전체적으로 최적의 해를 구할 수 있습니다.

 

동적 프로그래밍(DP)은 각 위치에서 가능한 최적의 값을 누적하여, 전체적으로 최적의 해를 보장합니다.

동적 프로그래밍 (DP) 설명

동적 프로그래밍은 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구하는 방법입니다. 이 문제에서는 각 행의 각 열에 대해 최적의 점수를 누적하여 최종적으로 가장 큰 점수를 구합니다.

왜 DP가 효과적인가?

1. 부분 문제의 최적해 이용: DP는 이전 행의 최적해를 이용하여 현재 행의 최적해를 계산합니다.
2. 중복 계산 방지: 이미 계산한 값은 다시 계산하지 않으므로 효율적입니다.
3. 전역 최적해 보장: 모든 가능한 경로를 고려하여 전역 최적해를 보장합니다.

 

 

응 이해못함