백준 15989번 1,2,3 더하기 4 해설/코드(파이썬) 다이나믹 프로그래밍 문제

풀이 코드만 궁금한 분은 깃허브링크 눌러주세요..!

GitHub - Rhyankwon/algorithms

 

문제 설명

결국 1, 2, 3을 적당히 잘 섞어서 어떤 수를 만드는데 그게 가능한 경우의 수를 모두 찾아야 한다.

 

문제 해결 논리 :

1. N이라는 값이 있을 때 그 값의 가능한 경우의 갯수를 dp[N]이라고 하자.

2. 이 때 dp[N]은 dp[N-1] + dp[N-2] + dp[N-3]이다. 그 이유는 N-1째에서 1을 더하고, N-2째에서 2를 더하고, N-3째에서 3을 더하는 것 모두 N을 만족하기 때문에 세 경우의 수를 모두 더해야 한다.

3. 이 때 1+1+3과 1+3+1같이 순서만 바뀐 경우는 같은 경우로 친다고 했으므로 1만 사용한 경우부터 순서대로 2, 3을 추가해야한다. (이게 무슨 말이냐면..)

3-1. 1만 사용하는 경우는 N까지 모두 한가지밖에 없다. 하지만 여기에 2를 추가한다고 하면, 3은 1+1+1뿐 아니라

1+2까지 두개가 가능하다. 5는 1+1+1+1+1(맨 처음 경우의 수)에다가 3+2까지 가능한데, 이 때 3을 만드는 경우의 수는 아까 두개엿으므로 총 3개 경우 ((1+2)+2, (1+1+1)+2 추가)까지가 가능하다. 이렇게 작은 수부터 1~N까지 순서대로,  그리고 1~3까지 차례로 값을 추가해야 중복되는 값 없이 경우의 수를 구할 수 있다.

4. dp[N]을 출력한다. 

 

이해가 잘 안되는 분은 천천히 다시 읽어보시면 될겁니다..!!!