고동치는고동

다익스트라와 dp를 사용한 문제 dp[x][y][k]로 dist배열을 선언한다.x,y까지 벽을 k만큼 뚫으면서 갔을 때 최단거리 기본적으로 bfs를 돌리면서 dp배열을 업데이트 시켜준다.que에는 다 넣을 필요 없이 dp배열을 업데이트 시킬 때마다 넣어준다. 출처 : http://wookje.dance/2017/02/22/boj-14442-%EB%B2%BD-%EB%B6%80%EC%88%98%EA%B3%A0-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-2/ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869..

출력범위가 int를 벗어나는 것을 주의하면 된다. 아무 노드나 루트 노드로 잡고 A노드에 있을 때, 자식 노드가 B, C, D가 있으면A노드는 자식 B, C, D가 요구하는 우물 중 가장 큰 수만큼 우물을 지으면 되고,A노드는 자신의 부모에게 자신이 필요한 우물에서 자신과 자식노드에 있는 우물의 수만큼을 뺀 값을 요구한다. 위 방식으로 dfs를 하면 최적의 값이 나온다.

쉬운 문제였지만 디스크립션을 이해하느라 오래 걸렸다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include int r, c, k;bool chk[1001][1001]; int dx[5] = { 0, -1,1,0,0 };int dy[5] = { 0,0,0,-1,1 };int gd[4];int cnt = 0; void f(int x, int y, int i) { chk[x][y] = true; int nx = x + dx[gd[i]]; int ny = y + dy[gd[i]]; if (nx == -1 || nx == r || ny == -1 || ny == c || chk[nx][ny]) { i..

12345678910111213141516#include typedef unsigned long long ull; int main(void) { int n; long long int sum = 0; scanf("%d", &n); ull prev = 0; for (int i = 1; i

곰팡이가 이동하는 것을 보면 좌푯값 i, j의 i+j가 짝수인 줄과 홀수인 줄이 독립적이라는 것을 알 수 있다.그리고 시간이 무한히 흘러간다고 가정하면 곰팡이가 한번 증식할 때마다 i의 좌표가 짝수->홀수, 홀수->짝수로 감을 알 수 있다. 따라서 초기 곰팡이의 위치가 4가지 경우가 모두 있으면 된다.i+j가 홀수고 i가 홀수i+j가 홀수고 i가 짝수i+j가 짝수고 i가 홀수i+j가 짝수고 i가 짝수 123456789101112131415161718192021222324252627#include #include using namespace std;bool chk[2][2]; int main(void) { int n, m, k; scanf("%d %d %d", &n, &m, &k); for (int i =..

간단한 매핑문제배열을 -1로 초기화 해놨지만 입력되는 증상이 배열의 크기를 초과해 고칠 수 없지만 0을 받아오는 경우가 생겼다.고쳐야하는 증상 S가 범위가 없음을 유의하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include using namespace std;int n, m;int arr[105];int brr[105]; int main(void) { int a; scanf("%d", &n); memset(arr, -1, sizeof(arr)); for (int i = 0; i

트리에서는 사이클이 존재하지 않기 때문에 단절선이 아닌 선은 없다.단절점 같은 경우 연결된 간선이 2개 이상이면 단절점이다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #define n_ 100005using namespace std; vector tree[n_]; int main(void) { int n, q, t, k; scanf("%d", &n); for (int i = 0; i

간단한 문제였지만 scanf가 아니라 cin을 써서 시간초과가 났다.검색해보니 cin이 scanf에 비해 엄청나게 느리다.앞으로는 scanf만 써야겠다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include typedef long long ull;using namespace std; ull sum = 0; int safe(int n,int m){ if (n

시간을 기준으로 1초씩 진행하며 구한다.현재 시간을 먹는 시간으로 나누었을 때 나누어 떨어지면 그때 그 사람이 소보루를 집어드므로 sum을 ++해준다.해주다가 먹은 소보루의 수와 같아지면 그때의 사람을 출력하면 된다. 그냥 다 해보면 된다. 12345678910111213141516171819202122232425262728#include #include using namespace std; int arr[100005];int n, s;int m; int main(void) { scanf("%d %d", &n, &s); scanf("%d", &m); for (int i = 0; i

i번째 길을 건널 때, i를 0부터 n까지 탐색하면서 최소가 되는 i를 찾고 마지막으로 계산함최소를 찾을 때 i번째 횡단보도를 건너게 되면 전보다 a[i]만큼 더가지만 b[i]만큼 덜가므로a[i] - b[i] 값을 한번 탐색할 때 마다 sum에 누적시키면서 시작했을 때보다 상대적으로 건너는게 이득인지 계산(음수일 경우 이득, cross는 제외하고 생각)그리고 매번 cross값을 sum에 더하면 상대적인 비용을 알 수 있으므로 min값을 업데이트 하면서 index 저장 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #define n_ 100005using namespace std..