목록Algorithm/dp (63)
Mini
[틀림] 프로그래머스 도둑질 // 노드스킵 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..
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()){ ..
[알고리즘] leetcode 790. 도미노와 트로미노 타일링 c++ // dp
* 완탐1. 타일의 종류정리하기2. 상태정의 : 열번호, 이전이 완전한지 여부long mod = 1e9+7;int n;class Solution {public: long dfs(int i, int prevgab){ if(i==n && prevgab==0){ //success return 1; } if(i==n && prevgab == 1){ //fail return 0; } if(i>n){ //out of index return 0; } //이전열이 빈칸이있는경우, if(prevgab){ return dfs(i+1,0) ..
[알고리즘] 리트코드 1696. 점프 게임 VI c++ // set, deque dp
https://leetcode.com/problems/jump-game-vi/ * 그냥 dppos N에대해 k번반복문 == O(N * K) -> 100억 -> 터진다. vector nums; int k;int dp[100000+4];class Solution {public: int dfs(int pos){ //pos에서 그때의 최대점수 if(pos==nums.size()-1){ return nums[pos]; } if(pos>=nums.size()){ //배제 return -987654321; } if(dp[pos]!=-1){ return dp[pos]; } ..