Mini

https://www.acmicpc.net/problem/4811 1.의사코드1. 알약을 1개꺼낸 경우 vs 반개꺼낸경우 계속 2분탐색이다.2. 완탐? -> 2^30 -> 불가 -> dp?3. 상태 : 큰알약갯수, 작은알약갯수 : 그때의 경우의수4. 경우의수는 기저사례 -> return 1, 후 +하면 된다.아래 그림과 같이 1이 리턴되고 거꾸로 타고오면서 그런 경우의 수가 모두 더해진다. 2. 전체코드#include using namespace std;typedef long long ll;ll dp[34][34];//큰알약남은갯수, 반알약남은갯수 : 그상태일때, 경우의수ll dfs(int a, int b) { if (a==0 && b==0) return 1; if (dp[a][b] != -1..

https://www.acmicpc.net/problem/1103 1. 사이클검사방법1. 방문한 좌표를 재방문했으면, 사이클이 있는것이다!! 2.중앙의 y,x에서 출발한경우, vis[y][x]=1 걸고들어간다탐색하면서 봤는데 vis[y][x]=1 이면, 빨간색경로로 갔다온것이다, 싸이클이 있는것임.이후, 원복을 해줘야함!원복안하는경우 : 우측의 2가 vis되있고, 다른경로(빨간경로)에서 2를 방문하면 사이클이 있는것으로 판단해버린다... 3. 의사코드if(visited) -1출력, 종료 visited = 1;상하좌우 탐색visited = 0;  2. 시행착오1. -1검사과정에서 상하좌우 같은수가 있으면 -1을 리턴하도록 했는데 이경우는1 11 1 에서는 먹히지만3 5 5 25 5 5 52 5 5 3 에서..

https://www.acmicpc.net/problem/170691. 의사코드1. dfs("끝" 좌표, 상태 :가로 세로 대각) 의 상태 기록이 필요함2. 기저사례 : 범위밖, 벽이있음 -> 해당 경우의수는 "0" 개로 처리 -> 배제시키기3. 좌표가 n-1인경우 -> 정답 -> 1개의 정답으로 처리.4. 논리부분 : 케이스에 맞게 [초기화, 논리, 리턴] 해주면 끝. 2. 시행착오1. 상태가 대각(2)일때 y-1, x-1도 벽인지 체크해줘야함2. dfs 호출부에서 (0,0,0)이 아닌 (0,1,0) 으로 호출해야함 // 끝좌표가 (0, 1) 이므로. 3. 전체코드#include using namespace std;typedef long long ll;ll n, a[33][33], dp[33][33][..

https://www.acmicpc.net/problem/1149 1. 의사코드1. 완탐 -> 3C1 을 N번반복 -> 3^1000 -> 불가2. dp? 3. 상태 : [idx][색깔] 1000(n개)*3(빨,노,파)에 가능!3.5 값 : 그 상태일때, 비용의 최소값4. 완탐기반으로, 위에서 칠한색을 제외한 2개중 최소값을 dp에 저장함. 2. 추가정보 필요시 해결방법위에서 무슨색을 칠했는지 알아야하기때문에 , b[idx] 배열에 기록해둠. 3. 전체코드#include typedef long long ll;using namespace std;int n, k,dp[1004][3],a[1004][3];int b[1004]; //해당 idx에 어느색을 칠했는지int dfs(int idx, int color) ..

https://www.acmicpc.net/problem/12865 1. 불가능한경우를 먼저 ret하라int dfs(int idx, int weight) { //기저사례 //!조건불만족하면 리턴! 이 return이 먼저와야함!! -> 그래야 배제가능. // 안그러면, 조건불만족 인데 idx==n인 경우도 유효한 경우로 카운팅됨. if (weight > k) { return -987654321; } if (idx == n) { return 0; }idx==n return 0이 먼저오는 경우 : 조건불만족인데 n에 도달한경우도 유효한 경로로 카운팅이 되어버린다.. 2. 의사코드0 번베낭을 담는다, 안담는다1번 베낭을 담는다 안담는다 ... 로 완탐하고dp[idx][weight] 의 상태를 배열에 저장해..

https://www.acmicpc.net/problem/2098 1. 외판원순회 특징1. {a,b,c} 집합을 "방문"한 상태에서 d로 가는 최소값과{b,a,c} 집합을 "방문"한 상태에서 d로 가는 최소값은 같다.즉, {a,b,c} 집합안에서 최소값인 경로(a->b->c 등)는 dp를 채우면서 저장된다.2. 2->3->1->2와3->1->2->2 는 같은 경로이다.따라서, 출발점은 아무거나(1번도시) 로 하자. 1.5. 비트 1111 만드는법1 하면된다!10000 -1 == 1111이렇게하면, 모든도시방문한 비트가 만들어진다! 2. 의사코드1. dfs(현재도시, 방문한도시체크용 비트)dfs(0, 1) 로 시작한다. //(0번도시부터 시작, 0번도시 방문표시==1)2. 기저사례 : 모든도시를 방문한경우..

https://www.acmicpc.net/problem/15486 15486번: 퇴사 2첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000)www.acmicpc.net 1. 의사코드1. 완탐기반, 상태를 배열에 저장함2. 상태 : idx==해당날짜3. 아래 그림을 그리고 참고하면서 max 식을 만들어낸다.max { 상담하는경우는 그때 이익을 더함 vs return 받은 이전값을 그대로 씀 }이값을 배열에 저장한다.#include typedef long long ll;using namespace std;//dp[i] : i날짜일때 최대수..

https://www.acmicpc.net/problem/2240 2240번: 자두나무자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어www.acmicpc.net1. 탑다운디피1. 디피는 기본적으로 "상태"를 "배열"에 저장하고이미 저장된 경로는 더 연산안하고 배열에 저장된 값을 사용하는 것이다.2. 이문제에서 "상태"는 {idx, 위치, 이동제한} 이다. 그 값은 그상태일때, 획득가능한 자두의 최대값이다. 2.비트연산자1. 나무위치가 1,2로 주어졌지만 이를 0, 1로 바꾸면 코드가 매우 간결해지는 장점이 생긴다.2. 장점 : if(0) , if(1)로 바로 활용가능..