목록Algorithm/dp (62)
Mini
[세모] 프로그래머스 완전범죄 // dp, void dfs dp
https://school.programmers.co.kr/learn/courses/30/lessons/389480?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr* 내풀이A가훔치기, B가훔치기 OX퀴즈 -> 2^40 -> 시간초과 -> dp 필요int dfs로 변경 && 메모참고로 dp 초기화부분을 상수시간 최적화해야 통과함..? 맞게푼건지? (재귀dp 억까?)import java.util.*;class Solution { static int n,m,ret=Integer.MAX_VALUE; // static int dp[][][] = new int[44][124][1..
[틀림] 백준 20181 꿈틀꿈틀 호석 애벌레 // 투포인터 dp
https://www.acmicpc.net/problem/20181* 시도1완전탐색방법상태 : index, 축적된에너지, 얻은탈피에너지, 이전에얻었는지(한번먹으면 계속먹어야함)O X로 완전탐색import java.io.*;import java.util.*;public class Main { static long ret, n, k; static long[] dp = new long[100000+4]; static ArrayList arr = new ArrayList(); // 축척된에너지, 얻은탈피에너지 static void dfs(int idx, long acc, long tal, boolean flag) { if(acc >=k){ tal += ..
[틀림] 백준 문자열 지옥에 빠진 호석 // 문자열, 먼저계산 dp, dfs
https://www.acmicpc.net/problem/20166* 시도110*10 이니까 그냥 dfs로 완탐하면 될듯? -> 시간초과100칸마다 각각 8방향 && depth 5제한 * 풀이미리 계산후, 쿼리하는 방식으로 개선시간복잡도 : 3,276,800(3백만) + 1000(조회)정답코드dfs가 과거풀이,dfs2가 캐시 미리계산 코드.string을 인자로 넘기는게 범인이 아니었음.import java.io.*;import java.util.*;public class Main { static int ret, n, m, k; static char[][] arr = new char[14][14]; static int[] dx = {0, 1, 0, -1, -1, 1, -1, 1}; ..
[맞음] 백준 2156 포도주시식 // dp
https://www.acmicpc.net/problem/2156* 풀이1. 완전탐색으로 시도 i번째 포도주를 먹는다 안먹는다.문제 : 연속3번은 안된다는것을 어떻게 검사하지?비트? -> n=10000개 의비트 -> 불가능cnt변수? (연속으로 선택한 포도주 갯수) -> 트리에서 O로 갈때 1씩 증가시키기!상태 : (idx, cnt) 값 : 그 상태일때, 최대값* 전체코드#includeusing namespace std; typedef long long ll;ll n;ll dp[10004][4];ll arr[10004];//인덱스, 연속선택카운트ll dfs(int idx, int cnt) { if(cnt>=3) { return -987654321; //배제 } if(i..
[틀림] 백준 1480 보석모으기 // 가방여러개 dp
https://www.acmicpc.net/problem/1480* 시도1N이작다? -> 조합이 여러번?(이 보석은 저가방에 넣고 ... 저 보석은 저가방에...) -> 비트마스크?무게작은순으로 정렬하면 되나?(그리디?) * 풀이그리디보다는 무식하게 완탐으로 시작할것.보석의 idx가 아닌, 가방의 상태들로 dfs 실행.상태를 생각해보자.[가방idx][남은용량][현재까지담은 보석의 집합]포인트는 가방기준 dfs, 현재까지담은 보석의 집합을 상태로 두는 것이다.현재가방에 보석을 담는다 or 안담는다로 완탐. & 메모보석은 for문으로 dfs내에서 완탐 필요.#includeusing namespace std; typedef long long ll;ll n,m,c;ll a[24];ll dp[14][24][1=..
[틀림 세모] 백준 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 ..