알고리즘/다이나믹프로그래밍(Dynamic Programming)
-
[백준-9095]-[다이나믹프로그래밍] - 1,2,3 더하기알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 8. 16:14
문제링크 : https://www.acmicpc.net/problem/9095 이문제는 다이나믹프로그래밍 공부하다보면 제일 기본문제로 나오는 문제이다.이런 문제가 공통점을 찾고 점화식 구하기가 제일 쉽다. 이런문제만 나왔으면 좋겠다. 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 숫자 1, 2, 3 으로 원하는 정소 n 을 만드는 경우의 수를 구하라 이다. 예제로 주어진 4로 구해보면 1+1+1+1 , 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1 총 7가지의..
-
[백준-1463]-[다이나믹프로그래밍]-1로 만들기알고리즘/다이나믹프로그래밍(Dynamic Programming) 2018. 11. 8. 15:29
문제 링크 https://www.acmicpc.net/problem/1463 DP 문제에서 중요한 점화식을 구해보고자 2부터 1이 되는 경우를 5정도까지 구해보았다. 2 같은 경우 {2 - 1, 2 / 2 } 정도가 있고 최소 횟수는 1 이다. 3 같은 경우 { 3 -1 -1 , 3 / 2} 가 있고 2로는 나눌수 없기 때문에 최소 횟수는 1 이다.4 같은 경우 { 4 -1 -1 -1 , 4 / 2 /2 , 4 -1 / 3 ) 등을 생각 할 수 있고 최소 횟수는 2 가 된다. 5 같은 경우 { 5 -1 -1 -1 -1, 5 -1 2/ 2 , 5 -1 / -1/ 3) 등을 생각할 수 있으며 최소 횟수는 3이 된다. 어느정도 공통점이 보이는거 같다. 2와 3은 일단 넘어가고 4와 5를 보자면 4에서 1을 빼..