[백준] 다이나믹 프로그래밍(DP) - "1, 2, 3 더하기" 시리즈

[시리즈 접근 방법]

 

** [1, 2, 3 더하기] 시리즈에서 중요한 것은 N을 만들기 위해 사용할 수 있는 숫자는 1 , 2 , 3 뿐이라는 것이다.

 

이 당연한 말이 뭐가 중요한가 싶겠지만,

사용 가능한 숫자가 1, 2, 3 뿐이라는 것은 dp[N] 에 영향을 줄 수 있는 원소들은

dp[N - 1] , dp[N - 2], dp[N - 3] 뿐이라는 것이다.

따라서 점화식 dp[N]은 dp[N - 1] , dp[N - 2], dp[N - 3]을 이용하여 만들어진다.

---

9095번 - 1, 2, 3 더하기

https://notorious.tistory.com/167

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 (!) (9095번 JAVA)

 

12101번 - 1, 2, 3 더하기 2

https://notorious.tistory.com/171

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 2 (!) (12101번 JAVA)

 

15988번 - 1, 2, 3 더하기 3

https://notorious.tistory.com/172

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 3 (15998번 JAVA)

 

15989번 - 1, 2, 3 더하기 4

https://notorious.tistory.com/173

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 4 (!) (15989번 JAVA)

 

15990번 - 1, 2, 3 더하기 5

https://notorious.tistory.com/170

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 5 (!) (15990번 JAVA)

 

15991번 - 1, 2, 3 더하기 6

https://notorious.tistory.com/175

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 6 (!) (15991번 JAVA)

 

15992번 - 1, 2, 3 더하기 7

https://notorious.tistory.com/176

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 7 (15992번 JAVA)

 

15993번 - 1, 2, 3 더하기 8

https://notorious.tistory.com/177

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 8 (15993번 JAVA)

 

16195번 - 1, 2, 3 더하기 9

https://notorious.tistory.com/178

[백준] 400 - 다이나믹 프로그래밍 1 : 1, 2, 3 더하기 9 (16195번 JAVA)

---

1,2,3 더하기 시리즈를 마치며 느낀점.

 

1부터 절반 가량은 혼자 점화식을 도출하지 못하였다.

점화식이 한눈에 보이지 않았고, dp 배열도 어떠한 형식으로 구성해야 하는지 감이 오지 않았다.

 

하지만, 문제를 점점 해결해 나가고, 다른 사람의 포스팅을 검색하여 이해해가며, 어느정도 감이 오기 시작하였다.

 

1, 2, 3 만을 사용한다는 것은 dp[n]의 점화식을 구성하는데 3개의 dp[] 배열의 원소가 사용된다는 것.

dp[] 배열은 2차원 배열로도 구성할 수 있다는 것이다.

dp[n][m] 중 m의 자리는 문제에서 내가 중점에 두고 싶은 값을 사용하여 해결한다.

예를 들어, '수식의 마지막 수' 라던가, '수식을 구성하는 수의 개수' 혹은 '수식을 구성하는 수의 개수가 짝수인가 홀수인가를 판단하는 flag' 등 이다.

 

점화식이 곧바로 도출되지 않을 때는 주먹구구식으로 dp의 원소들을 구해나가야 한다는 것도 깨닫았다.

 

앞으로 다양한 형식의 DP 문제도 이 경험을 활용하여 해결해 나갈 것이다.