[일반] 초보 dp문제 백준 1904

[laniake..(heecheon92)]

https://www.acmicpc.net/problem/1904

Baekjoon Online Judge

나 dp문제는 처음 접하는데

처음 시도할땐 무대뽀로 풀다가

각 n별로 값을 찍어 보니깐 (n - 1) + (n - 2)의 규칙을 찾아서 풀었거든? 근데 코드로 돌려보기 전엔 못찾았을거 같아.

형들은 dp문제 풀때 이런 규칙을 생각으로만 찾아내서 푸는편이야?

- dc official App

[익명(106.101)]

그냥 n에 해당하는 경우의 수를 하나하나 다 찍어보고 그 수열의 규칙을 찾아서 푸는 방식으로는 어려운 dp 문제들 대부분 풀지 못합니다.

[익명(106.101)]

핵심은 전의 값들과 현재의 값에 어떠한 관계가 있는지를 잘 파악하는 거죠. 위의 문제같은 경우에는 타일이 00, 1 밖에 없으니 현재 n에서의 경우의 수를 구하려면 n - 2 의 경우의 수에서 00 타일 하나 붙이는거랑 n - 1의 경우의 수에서 1 타일 하나 붙이면 되니 dp[n - 2] + dp[n - 1] = dp[n] 가 성립합니다.

[노는게제일좋아(aig0016)]

그렇게 풀 수 없는 dp가 앞으로 더 많긴 할 텐데, 입문은 어찌됐든 좋다고 생각해요

[익명(106.101)]

그리고, n - 2에서 00타일을 붙이면 모든 이진수들이 0으로 끝나고, n - 1에서 1타일을 붙이면 모든 이진수들이 1로 끝나니 둘 사이에 겹치는 경우의 수가 없으니 dp[n - 2] + dp[n - 1] = dp[n] 이 성립합니다.