mintuchel mintuchel

전형적인 DFS 사용한 조합론 문제이다. DFS 돌때 자신의 뒤 idx부터 호출하게 하고총 3개이면 조건판단해서 종료되게 하였다. 시간초과를 방지하기 위해3개를 조합하는 과정에서 M을 이미 넘어가게 되면 스킵하게 하였다 #include #include #include #define SIZE 101using namespace std;int N, M;vector arr;int ans = 0;void solve(int idx, int sum, int cnt){ // 종료조건이면 확인하고 return if(cnt == 3){ // 최신화가 안되어있었거나 지금꺼가 M에 더 가까우면 최신화 if (M - ans > M - sum) { ans = s..

DFS만 쓰면 시간초과가 난다따라서 DP로 못가는 경로는 미리 막아두어 다음턴에도 해당 경로로 탐색이 불가능하게 해줘야한다 이미 지나간 경로도 map[newy][newx] = 1 로 마킹하고 길이 없는 경로도 1로 마킹되게 해서 접근하지 못하게 하였다.#include #include using namespace std;int R, C;bitset map[10001];// 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래 순서로int dy[3] = {-1, 0, 1};int dx[3] = {1, 1, 1};int dfs(int cury, int curx){ // 종점 도달이면 if (curx == C - 1) { map[cury][curx] = 1; return 1;..

priority_queue + unordered_map 조합을 사용해도 되고처음부터 set을 사용해서 정렬과 중복제한을 한번에 보장받아도 된다 set이 그냥 중복 허용을 안하는 집합인 것만 떠올리면 안되고내부적으로 이진트리로 구현되어 있어 정렬도 보장하는 것을 꼭 명심하고 있어야한다 그리고 pair로 저장되기 때문에각 stl에 맞게끔 커스텀 정렬기준을 정의해줘야한다 이때 priority_queue는 return true가 우선순위가 더 낮다는 것을set은 return true일때 우선순위가 더 높다는 것을 조심해야한다 https://www.acmicpc.net/problem/1181 1. priority_queue + unordered_map 사용#include #include #include using..

맨처음에는 모든 정점을 BFS로 돌렸다 하지만 BFS로 돌릴 시 아래와 같은 경우에3을 먼저 방문하고 4까지 방문해서4가 visited 처리가 되면2번에서 4번에 방문하지 못한다  따라서 1 -> 4는 사실 2인데1 -> 4 가 201로 되서 4까지 못간다고 판단한다 따라서 각 N개의 노드에서 다른 노드로 가는 최적경로를 모두 구하고각 N개의 노드에서 타 노드로 R만큼의 거리 이내에서 갈 수 있는지 판단하는 식으로 풀어야한다 따라서 플로이드 워셜로 풀면 된다 #include #include #define SIZE 101using namespace std;int dp[SIZE][SIZE];int item[SIZE];int N, M, R;int main(){ ios::sync_with_stdio(0);..

DFS + DP 조합의 문제이다 하지만 맨 처음에는 DFS로 했다가 시간초과DFS + DP로 했다가 40%로 시간초과가 나서 뭐가 문제일까 하고 보니 답이 아닌 경로일때 최적화가 안된다는 문제가 되는걸 알았음 답이 안나오는 경우이면 내 코드 상 동서남북 훓고 sum의 기본값인 0을 반환함따라서 특정 dp 값이 0이면 해당 경로를 이미 탐색해봤는데 종점까지의 경로가 없더라~~ 인거임 그래서 경로가 없는 상황을 나타내는 값이랑 경로 탐색을 한번도 안한 상황을 나타내는 값을 구분하기 위해서탐색을 한번도 안한 상황은 dp값을 -1로경로가 없는 상황은 dp값을 0으로 하기로 함 그래서 초기에 모두 -1로 초기화 해주고 돌려야하고bfs 내부에서 dp값이 0이면 그냥 무시하게 해야함 https://www.acmicp..

벨만포드에 대한 정확한 이해와 원리를 알아야 풀 수 있다 그리고 벨만포드 내 사이클의 유무를 넘어사이클과 최적경로간의 관계에 대한 고민을 해야하는 문제이다 오민식의 고민과 같이 풀어보면 좋다 [벨만포드 적용 시 고려해봐야할 것들] 1. 벨만포드를 돌면서 최적경로 노드 순서를 어떻게 구할 것인가?-> 자신이 업데이트 되었을때의 간선 시작노드를 저장한다 2. 사이클 유무를 어떻게 파악할 것인가?> N-1번 돌린 뒤 한번 더 돌린다 3. 사이클과 최적경로의 관계는 몇개가 있는가?> 2개 4. 사이클을 구성하는 노드는 어떻게 저장할 것인가?> unordered_set으로 5. 사이클이 최적경로에 영향을 미칠 수 있다는 것을 어떻게 확인할 것인가?> 4번에서 구한 노드들 가지고 BFS를 돌린다 https://ww..

치즈를 한턴의 bfs를 돌때 녹이지 않는게 중요하다.bfs 돌때 녹여줘야하는 곳에 대한 정보를 저장해둔 후 bfs가 끝나고 녹여줘야한다. 치즈가 모두 없어질때까지 해야하므로치즈 유무를 파악하면서 bfs를 계속 돌리면 된다 #include #include #include #include #define SIZE 101using namespace std;int N, M;bitset map[SIZE];int dy[4] = {-1, 0, 0, 1};int dx[4] = {0, -1, 1, 0};int count_cheese(){ int cnt = 0; for (int i = 0; i > q; int cheese_touch[SIZE][SIZE] ={0,}; bitset visited[SIZE]..

얼핏보면 배낭 0-1문제랑 정말 비슷해보이는데제약조건이 있어 점화식이 달라진다 배낭문제는 담을 수 있으면 언제나 특정 물건을 담을 수 있었다하지만 이 문제는 특정 상담을 할 수 있는 경우가 하루에 그친다왜냐하면 한 개의 상담은 오직 해당 날짜에만 할 수 있기 때문이다그 점을 생각해서 점화식을 짜면 아래와 같이 나옴 DP 논리는 평범한 배낭과 동일하다내려가면서 특정 상담을 1개씩 더 고려한 결과가 나오는 것이다 #include #include #include #define SIZE 16using namespace std;int N;int dp[SIZE][1001] = { 0, };int W[SIZE], V[SIZE];void solve() { for (int i = 1; i > N; for (int i =..

맨 처음에는 조합이므로 DFS를 사용해 풀려고 했다하지만 DFS 쓰면 시간초과가 난다 따라서 DP로 2차원 배열 사용해서 풀었다하지만 메모리 초과가 남#include #include using namespace std;int N, K;vector v;int dp[101][10001] = { 0 };void solve() { // 각 줄의 0일때는 모두 1로 초기화 // 그래야 1, 2, 5에서 1개의 케이스가 더 추가됨 for (int i = 1; i = 0) { dp[i][k] += dp[i][k - v[i]]; } } }}int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int coin; cin >> N >> K; v.push_..