Algorithm/dp

[틀림 세모] 백준 14863 서울에서 경산까지 // dfs dp, ret초기값 주의

https://www.acmicpc.net/problem/14863* 풀이cnt#includeusing namespace std; typedef long long ll;struct A { int a,b,c,d;};int n,k,ret;ll dp[104][100000+4]; //(idx, num) : 그떄 경우의수vector v;ll dfs(int idx, int cnt) { if(cnt >n>>k; for(int i=0;i>a>>b>>c>>d; v.push_back({a,b,c,d}); } cout ret 초기화 문제처음풀이는 ret=0 -> 오답결론 : ret는 불가능 && 매우 큰값으로 초기화 하라!

[틀림 세모] 백준 5557 1학년 // dfs dp

https://www.acmicpc.net/problem/5557* 풀이+ , - 2가지 경우의수완탐 -> 2^100 -> 불가dp?#includeusing namespace std; typedef long long ll;int n;int arr[104];ll dp[104][24]; //(idx, num) : 그떄 경우의수ll dfs(int idx, int num) { if(num 20) { return 0; } if(idx==n-1) { if(num==arr[idx]) { // cout>n; for(int i=0;i>arr[i]; } // cout시행착오마지막 숫자와 같은지 검사, 마지막숫자도 더하거나 빼는것이 ..

[틀림] 프로그래머스 도둑질 // 노드스킵 dp

https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* dfs dp 풀이시행착오무조건 집을 다 도둑질하는게 이득아닌가?아님, 0원인집 도둑질 -> i+1에 100만원 집을 못텀결국 idx번째 집을 턴다, 안턴다로 완탐필요현재집을 턴다 -> 다음집은 cur+2 // cur+1을 못터는걸 여기서 구현현재집을 안턴다 -> 다음집은 cur+1다음집에서도 재귀적으로 위 2경우 탐색예외처리첫번째 집을터는경우, 마지막 집을 털수없음 예외처리#include using namespace std;int n;int ..

[틀림] 백준 2169 로봇조종하기 // 중복방문안된는 dp, 방향 dp

https://www.acmicpc.net/problem/2169* 헷갈렷던 부분2차원 dp로 안되는 이유dp, ret 초기화 값 문제국룰로 무조건 -1, 0 이 아님!-1, 0이 정답이 될수있는지 체크 필요!불가능한 값으로 초기화할것

[맞음] 백준 1535 안녕 // 갯수1개 제한 dp

https://www.acmicpc.net/problem/1535* 풀이갯수제한dp는dfs(idx, 상태)로 풀면 되는듯?for문으로 할꺼면 뒤에서부터 채우기#includeusing namespace std; typedef long long ll;int n;int hp[24], gi[24];ll dp[24][104];ll dfs(int idx, int cnt) { if(cnt >n; for(int i=0;i>hp[i]; } for(int i=0;i>gi[i]; } cout

[틀림] 백준 1513 경로찾기 // 4차원 dp, 경로찾기 dp , 경우의수 dp

https://www.acmicpc.net/problem/1513* 시도1한번에 탐색후dp[y][x][오락실cnt]로 출력하면?문제점else if 남발보다는 종료조건 사용할것ret+=가 아니라 ret = ( 좌dfs + 우 dfs) 형태가 맞음.트리그린후, 재귀로 이해#includeusing namespace std; typedef long long ll;int n, m, c;int a[54][54];ll dp[54][54][54]; // y, x, 오락실 번호: 경우의 수const int mod = 10000007;ll dfs(int y, int x, int cnt) { if(y n || x > m) { return 0; // 범위 밖 } if(y == n && x == m) { ..

백준 4781 사탕가게 // dp, 갯수무한인경우는 dfs내 for문, 소수처리방법

https://www.acmicpc.net/problem/4781* 시도1사탕선택 o,x로 하면될듯?갯수가 무한대임 -> 불가능 * 풀이갯수가무한대인경우 , 상태를 dfs(남은돈) : 그때 최대칼로리로 정의, idx는 제거dfs내 for문으로 완탐필요!!for내에서 가능한경우, 노드를 계속생성함!!소수처리방법1scanf로 받아서 각각처리또는 cin으로 받아서 round 처리 #includeusing namespace std; typedef long long ll;int n;double m;vector> v; //칼로리, 가격ll dp[10000+4]; //돈(m) 최대 : 10000원ll dfs(int money) { if(money =0) { ret=max(ret,dfs(money-v..

[알고리즘] 416. Partition Equal Subset Sum c++ 리트코드 // 완탐, dp

https://leetcode.com/problems/partition-equal-subset-sum/solutions/1624939/cpython-5-simple-solutions-w-explanation-optimization-from-brute-force-to-dp-to-bitmask/* 완탐-내생각 : 200C1 + 200C2 + 200C3 + ,... + 200C 200 == 2^200 //빡세다..-답 : 이진트리로 쉽게생각하면됨 // num[idx]를 sum1에 넣기 or sum2에 넣기 == 2^200vector nums;class Solution {public: int go(int idx, int sum1, int sum2){ if(idx>=nums.size()){ ..