jmmm_25

DP 문제이다. cache[i][0] = min(cache[i-1][1], cache[i-1][2]) + board[i][0];cache[i][1] = min(cache[i-1][0], cache[i-1][2]) + board[i][1];cache[i][2] = min(cache[i-1][0], cache[i-1][1]) + board[i][2]; 이 부분이 핵심이므로 디버깅 다시 해보면 될 것 같다. 1234567891011121314151617181920212223242526#include #include #include using namespace std; int board[1001][3];int cache[1001][3];int N; int main(int argc, char const *argv..

문제의 핵심은 순서대로 치즈를 먹는다 이다. S -> 1 -> 2 -> 3 -> ... -> N 이므로, S -> 1 찾으면 BFS를 끝내고, 1 -> 2, 2 -> 3 이런식으로 찾아가면 된다. 만약 못먹을 경우에는 dist만 큐가 빌때 까지 늘려주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #include #include using namespace std;class Node {public: int x, y, dist, level; Node() {}; Node(int _x, int _y,..

DP로 점화식만 알면 풀 수 있다. 1234567891011121314151617181920212223242526272829#include #include #define ll long longusing namespace std; int n, m, test;int cnt = 0;ll cache[40][40]; ll sol(int f, int h){ ll &ret = cache[f][h]; if (f == 0 && h == 0) { return 1; } if (ret != 0) return ret; if (f != 0) ret += sol(f - 1, h + 1); if (h != 0) ret += sol(f, h - 1); return ret;} int main(int argc, char const *ar..

문제에서 3가지의 연산이 있다./3, /2, -1 따라서 이 3가지의 경우로 DP로 풀면 된다. 1의 경우에는 만족하는 경우가 없으므로 0 --> cache[1] = 02의 경우에는 /2 or -1의 경우 만족하므로 --> cache[2] = 13의 경우에는 /3의 경우가 만족하므로 --> cache[3] = 1이다. 힌트에서 10의 경우에는 10 -> 9 -> 3 -> 1의 경우이다. sol(10-1) +1 의 경우가 답이 될 것이다. 10 - 1을 해서 9를 만들고 cache[9]에 저장된 값을 불러오면 최소 연산으로 1을 만들 수 있을 것이다. 4의 경우에는4 -> 2 -> 14 -> 3 -> 1이렇게 2가지의 경우가 있다. 따라서 sol(4 - 1) + 1 = sol(3) + 1 = 1 + 1 =..

DP 문제점화식만 잘 세우면 된다.DP[1] = 1DP[2] = 2DP[3] = 4 DP[4] = DP[1] + DP[2] + DP[3] = 7 이다. 따라서 점화식은 DP[i] = DP[i - 3] + DP[i - 2] + DP[i - 1] 이다. 1234567891011121314151617181920212223242526272829303132#include #include using namespace std; int cache[11];int T, N;int sol(int n) { int &ret = cache[n]; if (ret != -1) return ret; if (n == 1) return 1; if (n == 2) return 2; if (n == 3) return 4; ret = sol(..

벽 부수고 이동하기 1과 비슷한 문제이다. 이 문제는 K 인자가 추가되어 벽을 K개의 갯수만큼 부실 수 있다.1 문제에서는 1번만 부실 수 있으므로 visit 배열을 [2]까지만 잡았지만, 이 문제는 K번 부실 수 있으므로 visit[10] (1

BFS 탐색으로 풀 수 있는 문제이다. 우선 (1,1)의 좌표에서 시작하여 board == 0 인 곳으로 이동을 한 뒤, 벽을 만나게 되면 now.broken이 0일 경우만벽을 부수고, 벽이 아닌 곳으로만 이동하면 되는 문제이다. 단, 벽은 1개까지만 부실 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include using namespace std;class Node {public: int x, y, dist, broken; Node() {}; Node(int _x, int..

dfs로 모든 경우를 다 탐색하면 된다. 숫자는 변하지 않으므로 고정시키고 연산자만 for문과 재귀로 다 쓰면 된다.다시 한번 풀기!!!최대, 최소값은 10억이므로 처음에 초기화를 시켜주었다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #define INF 1000000000#define ll long longusing namespace std; int N;int op[4];int number[12];ll int Max = -INF;ll int Min = INF; void dfs(int depth, ..

말 그대로 주사위가 동, 서, 남, 북 으로 굴려졌을 때 어떻게 옮겨지는지를 구현하면 된다.너무 노가다로 푼 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132#include #include using namespace std; int ..

이 문제는 무조건 3개의 벽을 세워야 하므로, 벽 부터 세워야 한다. dfs를 이용해 벽을 세운 뒤 bfs 탐색을 통해 바이러스를 퍼뜨리고 안전 영역의 갯수를 세면 된다.벽 세우는 것이 조금 까다로운 문제였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include #include #include using namespace std; int N, M, ret = -9876543;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0 ..