https://www.acmicpc.net/problem/14500 브루트 포스로 모든 좌표에 대하여 테트로미노의 모든 경우의 수인 19가지를 살펴보면 된다. 탐색 횟수가 최대 500*500*19*4=19000000 이므로 시간 내에 충분히 돌아간다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include using namespace std; int n,m,map[510][510],ans;pair d[19][4]={ {{0,0},{0,1},{0,2},{0,3}}, {{0,0},{1,0},{2,0},{3,0}}, {{0,0},{0,1},{1,0},..
https://www.acmicpc.net/problem/1937 판다가 대나무를 먹으면서 이동한다. 단, 현재 위치의 대나무보다 더 많은 대나무가 있는 쪽으로만 이동한다. 이 때 판다가 이동할 수 있는 최대 길이를 찾는 문제이다. 먼저 DFS를 이용한 완전 탐색을 생각해 볼 수 있다. 그러나 N이 최대일 때, 500*500의 map에서 모든 경로를 다 탐색하면 시간 초과가 나게 된다. 이 때 다이나믹을 이용해서 가지치기를 한다. d[x][y] = 판다가 (x,y)까지 올 수 있는 최대 길이라고 정의하자. 경로를 탐색하다가 d[x][y]가 지금까지 온 경로의 길이 k보다 크다면 이미 다른 경로로 왔을 때의 최대 길이가 존재한다는 뜻이다. 이 경우 더 이상 탐색하는 것이 의미가 없으므로 탐색을 종료한다. ..
https://www.acmicpc.net/problem/8006 K번째 최단경로 찾기와 같은 문제인데 쿼리로 최대 10000개가 들어오므로 매번 구한다면 시간 초과가 난다.D[S][E][K] = S에서 E로 가는 K번째 최단경로의 길이라고 하고 미리 쿼리를 다 구해놓고 각 쿼리마다 D 배열값을 출력해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include #include #include using namespace std; int n,m,a,b,c,q,s,e,k;int d[101][101][101];vector adj[..