Algorithm/dp

백준 11727 2*n 타일링2 c++ // dp

https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 1.전체코드 #include using namespace std; long long d[1004],n; //2*i 직사각형을 채우는 방법의 수 //d[i]= //첫째사각형 1*2인 경우 : d[n-2] //첫째사각형 2*1인 경우 : d[n-1] //첫째사각형 2*2인 경우 : d[n-2] int main() { ios_base::sync_with_stdio(0); cin.tie(0); d[1] = 1; d[2] = 3; ci..

백준 1003 피보나치 함수 c++ // dp

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 전체코드 #include using namespace std; int t, n; int d[44][2]; //1.테이블정의 // d[i][0] : fibo(i)에서 0이 출력되는 횟수 // d[i][1] : fibo(i)에서 1이 출력되는 횟수 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n - 1) +..

프로그래머스 43105 정수삼각형 c++ // dp , 인덱스에 주의하자, 일반식을 정확하게 짜는방법

https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 일반식을 정확하게 짜는방법 오류 : if(j==i)우측 끝일때 d[i][j]=d[i-1][i] 해결 : if(j==i)우측 끝일때 d[i][j]=d[i-1][i-1] 아래그림에서 d[0위치]=d[8위치]==d[i-1][i-1]이 되어야한다! 2. 전체코드 #include using namespace std; int dp[504][504]; //1. d[i][j] : i높이에서 누적 최대합. ..

백준 12852 1로만들기 2 c++ // dp, 경로복원 하는 방법 pre[i]

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. 경로복원 하는 방법(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[100..

백준 11659 구간합구하기4 c++ // dp, dp를 사용해야할때 아는방법

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

백준 11726 2*n타일링 c++ // dp, 점화식세우기

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]과 같음 * 첫사각형을 ㅡ 로 두는경우-> 밑에도 ㅡ로 둬야함 -> (두줄..

백준 1149 RGB거리 c++ // dp, 테이블정의(2차원)

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

백준 2579 계단오르기 c++ // dp , 제약조건이 있으면 2차원 dp로 테이블을 정의하라.

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]은 안밟 ..