Algorithm/dp

백준 9095 1,2,3더하기 c++ // dp 기준으로 나눠서 규칙을 찾아라

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 1. 풀이과정 및 전체코드 d[4]를 기준(맨끝에 더하는수)로 정렬후 규칙을찾고 일반화 한다. #include using namespace std; /* * DP * 1. 테이블정의 * 2. 점화식 for문 */ //1. d[i] : i를 1,2,3의 합으로 나타내는 방법의 수 /* * d[1]=1 * d[2]=1+1 d[1] / 2 / * d[3]=1+1+1 d[1] / 1+2 d[2]+1 / 2+1 d[2]+1 / 3 / * 기준 : 맨뒤에 더하는 숫자 * d[4]=1+1+1+1, 3+1, ..

백준 1463 1로만들기 c++ // dp 하는 방법

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. dp 하는 방법 /* * DP * 1. 테이블정의 * 2. 점화식 for문 (초기항은 직접구함) */ 1.1 점화식 구하는방법 구체사례를 일반화 하라. d[12] = d[4]+1 , d[6]+1 , d[11]+1 중 최소값 d[i] = d[i/3]+1 , d[i/2]+1 , d[i-1]+1 중 최소값 2. 최소값 구하는 방법(3개숫자 이상일때) 첫번째 값 대입후 새로운 값이 들어올때마다 min (자기자신, 새로운값) 해주면 된다. d[i] = d[i - 1] + 1; if (i % 2 == 0) { d[i..