반응형
Baekjoon
-
백준 2193 - 이친수백준 algorithm 2020. 4. 23. 17:39
=> DP 문제이다. => DP [i][j] => i : 몇 자릿수인지 나타냄 => j : 어떤 숫자로 끝나는지 나타냄 DP[i][0] = DP[i-1][0] + DP[i-1][1] => 0으로 끝나는 수의 경수, 앞의 수가 1이어도 되고 0이어도 된다. DP[i][1] = DP[i-1][0] => 1으로 끝나는 수의 경수, 앞의 수가 0이어야 된다. 위의 식대로 풀어도 된다. 본인은 하나씩 손으로 풀어보며 식을 세우게 되었다. DP[i] = DP[i-1] + DP[i-2] => 위의 식을 통해 원하는 값을 얻을 수 있다. #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr)..