Mini

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.www.acmicpc.net1. 경로복원 하는 방법(1) : pre[i] : i는 pre[i]로 가는게 최선이다.pre[3] =1  : 3은 1로 가는게 최선임. 2.바킹독 코드// Authored by : BaaaaaaaaaaarkingDog// Co-authored by : -// http://boj.kr/da0497aabb26436c9ae613785cb439f7#include using namespace std;int d[1000005]; //d[i] : i를 1로만드는데 필요한 연산의 최소값int pre[1000005];// ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 1. dp를 사용해야할때 아는방법 완탐 : O(NM) -> 100억 ->불가능 해결 : dp, greedy를 생각하면 된다! 2. 전체코드 누적합이용하면 된다. #include using namespace std; /* * DP * 1. 테이블정의 * 2. 점화식 for문 */ /* * 1. 테이블정의 * d[i] : d[1]~d[i]번째까지의 누적합 * 2.점화식 d[k]..

https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 1. 문풀 및 전체코드 #include using namespace std; /* * DP * 1. 테이블정의 * 2. 점화식 for문 */ /* * * 1. 테이블정의 * d[i]: 2*i크기의 직사각형을 채우는 방법의 수 * |||||||||| * |||||||||| * * d[k] : 첫사각형을 |로 두는경우 -> (맨앞줄제거한)d[k-1]과 같음 * 첫사각형을 ㅡ 로 두는경우-> 밑에도 ㅡ로 둬야함 -> (두줄..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1. 문풀 및 전체코드 #include using namespace std; //i번째 집을 j색으로 칠했을때 최소비용, 칠한색깔(0:빨, 1:초, 2:파) int d[1004][3], a[1004][3]; int n; /* * d[1][0] * d[1][1] * d[1][2] * * d[k][0] : max(d[k-1][1]+a[k][0], d[k-1][2]+a[k][0])..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1. 전체코드 #include using namespace std; /* * DP * 1. 테이블정의 * 2. 점화식 for문 * 3. 초기값 정하기 */ /* * * 1. 테이블정의 * d[i][j] : 현재까지 j개의 계단"연속" 밟음, i번째 계단까지 왔을때 점수합의 최대값 i번째 계단을 꼭 밟아야함. 2.점화식 d[k][1] : k번째 계단까지왓는데 "연속" 1개밟음->자기자신임->d[k-1]은 안밟 ..

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, ..

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..