저같은 경우는 일단 dp를 선언하고 옆에다가 주석으로 dp[i][g]가 뭔지 선언하고 풉니다.
예를 들어 이 문제를 푼다고 했다면
변수를 선언 할때 밑에와 같이 dp[i]가 무엇인지 정의 해줍니다.
int dp[1001] = {}; //dp[i]는 크기가 i인 직사각형을 채우는 방법의 수
라고 지정한 다음
선생님 처럼 살짝 노가다를 하여 규칙성을 파학합니다.
크기가 i인 직사각형을 채우는 방법은
1. 크기가 i-1인 직사각형을 채우는 방법의 +1이다,(세로로 긴 사각형1개만 가능함)
2. 크기가 i-2인 직사각혀을 채우는 방법의 *2이다.(가로로 긴 사각형 2개와, 정사각형 1개가 가능함)
그리고 마지막으로 dp[1],dp[2]만 수작업으로 채워준 뒤
점화식 dp[i]=dp[i-1]+ 2*dp[i-2];을 이용하여 값을 구합니다.
exon 2년 전 3
알고리즘을 배우기 시작한지 1주 되지도 않은 초보입니다.
최근에 DP 문제들을 푸는데,
이 문제를 포함해서 대다수의 DP 문제를 노가다를 하고 규칙을 찾는 방법으로 풀고 있습니다.
이 문제를 예로 들자면,
dp[1] = 1
dp[2] = 3
dp[3] = 5
dp[4] = 11
dp[5] = 21
이정도 직접 풀이해서 규칙을 찾는 방법을 찾는데
(물론 단순한 규칙만으로 풀지 못하는 문제들이 적지 않지만)
이런 문제들은 고수분들도 직접 풀이해서 규칙을 찾는 방법을 쓰시나요?
짧지 않은 글 읽어주셔서 감사합니다!!