dp문제

생각의 방향 dp 문제라는 것을 알고 문제에 숨겨진 규칙을 찾아내려 애썼다. 이전에 (2xn 타일링) 문제는 그리지 않고 직접 경우의 수를 적어서 문제를 풀었다. 이번에는 직접 도형을 그려서 점화식을 찾으려고 했다. 그런데, 그려도 모르겠는거다... dp 문제의 핵심은 이전에 계산한 값을 저장해뒀다가 사용하는 것이 핵심인데, 이전의 값이 어떻게 쓰이는건지 잘 보이지 않았다. 계속 시도해보고 다시 생각해서 결국 아래와 같은 점화식을 도출했다. //n이 짝수인 경우 dp[i] = dp[i-1] * 2 + 1 //n이 홀수인 경우 dp[i] = dp[i-1] * 2 - 1 n이 짝수인 경우와 홀수인 경우, 이전 수열 값의 x2 + 1 값으로 원하는 답이 나오는 것을 알았다. 해당 점화식을 적용한 코드를 제출하..