dynamic programming

[BOJ] 25421. 조건에 맞는 정수의 개수

https://www.acmicpc.net/problem/25421 25421번: 조건에 맞는 정수의 개수 2개의 자릿수를 갖고 첫 번째 자리의 숫자와 두 번째 자리의 숫자의 차이가 2보다 작거나 같은 양의 정수 11, 12, 13, 21, 22, 23, 24, 31, 32, ... , 97, 98, 99가 A에 해당된다. 따라서 정답은 39이다. www.acmicpc.net 문제 분석 & 풀이 간단한 DP문제다. 많이 가볼 필요 없이 n=3까지만 손으로 세보면 규칙을 쉽게 파악할 수 있다. 점화식은 dp[n][i] = dp[n-1][i-2] + dp[n-1][i-1] + dp[n-1][i] + dp[n-1][i+1] + dp[n-1][i+2]. 1, 2, 8, 9일 때 예외처리만 신경쓰면 된다. 코드 ..