[BOJ] 16988. Baaaaaaaaaduk2 (Easy)
*조합을 이용하여 2개의 빈칸 좌표에 내 돌(1)을 놓은 후, 죽일 수 있는 상대 돌의 최대값을 계산한다. *죽일 수 있는 상대 돌 그룹은 내 돌(1)로 둘러싸여져 있어야 한다. 하지만 그것을 증명하는 것보다는 돌 그룹의 상하좌우에 빈칸(0)이 있으면 그 돌 그룹은 죽을 수 없다고 간주하는 것이 더 구현하기 쉽다. #include #include #include #include using namespace std; int n, m, ans = 0; int map[21][21]; typedef pair pp; vector emt, enemy; int emtCnt = 0; bool visited[500], chk[21][21]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1..
[BOJ] 1520. 내리막길
*dfs와 dp를 이용하여 풀이 *도착 지점(m-1, n-1)부터 시작해서 (0,0)에 도착하면 1을 리턴하여 갈 수 있는 경로임을 저장한다. *만약, 이미 한 번 지나온 곳을 다시 가게 되면 중복 탐색을 할 필요가 없기 때문에 저장된 값을 리턴해준다. *모두 탐색했을 때 dp[m-1][n-1]에 저장된 값이 정답이다. *길을 중복 탐색하지 않아야 TLE를 피할 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int m, n, ans = 0; int map[501][501]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; int dp[501][501]; bool..