DP 5

백준 12852번 1로 만들기 2 ( C++ )

문제https://www.acmicpc.net/problem/12852 해설경우의 수만 구하면 된다면 dp를 이용해서 간단하게 구할 수 있음하지만 이동 경로를 표시해야 하기 때문에 그 점을 기록하기 위한 last배열을 선언재귀를 통해 구현하였을 경우 깊이 문제가 발생하여 반목문으로 해결 코드12345678910111213141516171819202122232425262728293031323334353637383940#includeiostream>#includealgorithm> using namespace std;typedef long long ll; int n, visited[1000004],last[1000004]; void go(int num) {    visited[1] = 0;     for (..

백준 4811번 알약 ( C++ )

문제https://www.acmicpc.net/problem/4811 해설dp로 풀어야 하는 문제임은 빠르게 알 수 있으나 어떻게 풀지 조금 걸린 문제온전한 알약과 반만남은 알약을 기준으로 문제를 해결 코드12345678910111213141516171819202122232425262728#includeiostream>#includealgorithm>#includecstring> using namespace std;typedef long long ll; int n;ll dp[34][34]; ll go(int full, int half){  if(full == 0 && half ==0) return 1;  ll &ret = dp[full][half];   if(ret) return ret;  if(half..

백준 2240번 자두나무 ( C++ )

문제https://www.acmicpc.net/problem/2240 해설경우의수가 너무 커서 dp로 해결-1로 초기화 할 경우 ~ret을 사용하면 -1일때만 false를 반환하도록할 수 있음 코드12345678910111213141516171819202122232425#includeiostream>#includealgorithm>#includecstring> using namespace std; int t,w,dp[1004][2][34], mv[1004]; int go(int idx, int location, int cnt){  if(cnt  0) return -10000;  if(idx >= t) return 0;  int &ret = dp[idx][location][cnt];  if(~ret) re..

백준 1103번 게임 ( C++ )

문제https://www.acmicpc.net/problem/1103 해설모든 경우의 수를 고려할 경우 (50*50)의 4제곱이 되기 때문에 dp를 이용해서 해결 코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#includeiostream>#includealgorithm> using namespace std; int n,m,dp[54][54], ret;char mp[54][54];int dy[4] = {-1,0,1,0};int dx[4] = {0,1,0,-1};string line;void go(int y, int x, int cnt){  if(cnt > n*m){    ..

백준 2098번 외판원 순회 ( C++ )

문제https://www.acmicpc.net/problem/2098 해설단순히 모든 곳을 방문하는 문제면 간단 dp문제 이지만 순회를 해야하는 조건이 조금 까다로움순회를 확인하기 위해 비트마스킹 사용 코드123456789101112131415161718192021222324252627282930313233343536373839404142#includeiostream>#includealgorithm>#includevector>#includecstring> using namespace std; const int INF = 987654321;int n,start[20],end[20],s,e,cost, dp[20][1(16)],mp[20][20];vectortupleint,int,int>> v;vectorve..