홍시홍의 프로그래밍

분류 : dp 요구사항 n이 주어졌을때 1, 2, 3으로 n을 만들 수 있는 경우의 수 구하기 풀이 n을 만들기 위해서 d[n-1] +d[n-2] + d[n-3] 으로 만들 수 있다 n-1에서 1을 더하면 n n-2에서 2를 더하면 n n-3에서 3을 더하면 n이 된다 1, 2, 3으로 만들 수 있는 경우의 수는 위 3가지 이다 #include #include #include //#include "windows.h" #include #include using namespace std; int d[14]; int main(){ int t; scanf("%d",&t); for(int tc=1;tc=4){ for(int i=4 ; i

분류 : dfs+bfs 요구사항 배양액을 알맞게 뿌려 피울 수 있는 꽃의 최대 개수 구하기 풀이 1. DFS로 배양액을 뿌릴 장소 구하기 2. DFS로 장소에 어떤 배양액 뿌릴지 구하기 3. BFS로 꽃이 피는가 선택 3번은 (1)레드배양액 먼저 이동하고 (2)블루배양액 이동하는데 두개 이동이 끝나고 두개가 도착한 곳이라면 꽃으로 표시한다. 꽃으로 표시하고 꽃이 핀 부분에는 이동 못하니깐 따로 표시해준다 코드가 많이 지저분하다.. #include #include #include #include #include using namespace std; struct go { int x; int y; }; int n, m, r, g; int map[55][55]; int visit[55][55]; int Pvis..

분류 : DP 요구사항 쉬운 계단의 숫자 구하기 인접한 숫자의 차이가 1인 수 구하기 풀이 손으로 2~3까지 적다보면 점화식이 보인다 1자리는 9개 1자리의 쉬운 계단 수에다가 -1, +1를 더한 값이다 이를 점화식으로 나타내면 d[i][j] = d[i-1][j-1] +d[i-1][j+1]이다 하지만 0과 9일때는 예외 처리해준다 #include #include using namespace std; int n; int d[110][10]; int main() { scanf("%d", &n); d[1][0] = 1; for (int i = 1; i

분류 : DP 요구사항 원하는 카드의 갯수가 주어질때 카드 값을 최대로 지불하는 금액 구하기 풀이 d[i]는 i개의 카드를 보유하고 있을때의 최대 값이다. d[i]는 i*map[1]로 초기화한다. d[i] = max(d[i], map[i-j] +d[j])의 점화식으로 구한다 d[j]는 이미 앞에서 구했던 현재 j까지의 최대 값이 된다 #include #include using namespace std; int n; int d[100100]; int map[1010]; int main() { scanf("%d", &n); for (int i = 1; i