[백준][C++] 9095 1, 2, 3 더하기

9095. 1, 2, 3 더하기 문제 풀이 DP가 바로 이거구나! 알게 된 문제.

조금 고민해보다가... 생각해보니까 1을 만들 수 있는 연산, 2를 만들 수 있는 연산, 3을 만들 수 있는 연산을 가지고 계속 계속 다른 연산을 만들어가다보면 정답이 나오게 되는 것이었다!

만약에 4를 만든다고 하면... input => 4 1 => 1 arr[1] = 1 2 => 1+1 2 arr[2] = 2 3 => 1+1+1 1+2 2+1 3 arr[3] = 4 4 => 4 = arr[1] + 3 4 = arr[2] + 2 4 = arr[3] + 1 이므로... arr[4] = 1 + 2 + 4! answer => 7 코드로 구현해봤다.

#include using namespace std; int main() { i.....