다이나믹 프로그래밍 문제 정리

지금까지 다이나믹 프로그래밍 문제를 풀면서 파악한 것으로

배열은 입력받는 배열, 정답을 담을 dp배열 이렇게 두가지를 선언하고

dp배열에 최대값 또는 최소값 등 구하는 값을 넣어 마지막에 dp[n]을 출력하는 공통점이 있었다. 

 

접근할 때 생각할 것들을 정리하면

• 구하는 값 - dp에 들어갈 값 즉, 그 문제의 정답
  - 내 경우에는 dp배열에 들어가는 값이 무엇인지 문제를 풀면서 도중에 길을 잃을 때가 있었다. 입력받은 배열과 dp배열을 정확하게 구분하자
• 문제의 조건
  - 조건을 정리하는 것은 문제를 이해하는 방법중 하나인데 때로는 조건을 놓쳐서 틀린 경우가 있었다.
• 문제 접근방법
  • 타일채우기 등 타일의 모양에 따라 달라지는 방법의 수를 구하는 문제는 그림으로 접근 
  • 이친수 등의 문제는 케이스마다 표로 정리하면 점화식 규칙이 눈에 보였다. 이렇게 푸는 문제가 꽤 있었던 것 같다.
  • 스티커(9465), 포도주 문제(2156), 카드 구매하기(11052) 등 i번째 항과 그 전에 있던 항을 비교하여 큰 값 또는 작은 값을 넣어주어서 푸는 문제가 있다. 이 문제는 하나씩 대입해서 푸는 것으로는 잘 파악이 되지 않는 것 같다. 그 전에 있는 dp[] 배열에 있는 것과 입력받은 것을 연산해서 그 값이 dp[i]번째 항과 비교해 큰 값인지 작은 값인지 판단하여 대입한다.