Inflearn Community Q&A
asked
7-B 이 방식은 완탐방식일까요?
Written on
·
390
·
Edited
0
http://boj.kr/a788644d92fe4bc5bb99fe02b91e1f46
항상 감사드립니다. 문제 풀기 전 최대 3가지방향과 16개의 범위로 3^16 이겠거니 완탐은 불가능하겠다. 생각하고 문제를 풀기 시작했는데요..
막상 풀고 선생님 코드를 보니 제 코드는 완전탐색으로 푼것같은 느낌이 들어서 질문드립니다.
사실 시간초과가 나야 정상인 코드가 아닌가 싶어 질문드립니다.
Quiz
동적 계획법(Dynamic Programming)을 적용하기 위한 주요 조건은 무엇일까요?
탐욕적 선택 속성, 최적 부분 구조
최적 부분 구조, 중복되는 부분 문제
중복되는 부분 문제, 결정론적 결과
탐욕적 선택 속성, 메모이제이션
Answer 2
0
아 제가 질문을 잘못드렸네요 제 코드가 완탐인 것 같아서 확인차 질문했었습니다 역시나 완탐이었군요 DP로 다시 풀어보겠습니다.
혹시
격자판의 크기가 n x n이므로, 이동하는 것을 고려하면 -> 대각선으로 이동할 때 최소값인 2n-1입니다. 하지만, 실제로는 가로 또는 세로로만 이동하는 경로도 고려해야 하므로, 경로의 최대 길이는 2n보다 클 수 있습니다. 그래서 얼추... 3^32가 되는 것이죠.
이 부분이 이해가 잘 안갑니다 ㅜㅜ 혹시 추가 설명이 가능할까요?
0
안녕하세요 mch님 ㅎㅎ
일단 제코드는 완탐이 아니라 DP이긴 합니다.
#include <bits/stdc++.h>
using namespace std;
void fastIO(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int n, a[24][24], dp[24][24][3];
bool check(int y, int x, int d){
if(d == 0 || d == 2){
if(!a[y][x]) return true;
}else if(d == 1){
if(a[y][x] == 0 && a[y - 1][x] == 0 && a[y][x - 1] == 0) return true;
}
return false;
}
int main(){
fastIO();
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
cin >> a[i][j];
}
}
dp[1][2][0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(check(i, j + 1, 0))dp[i][j + 1][0] += dp[i][j][0];
if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][0];
if(check(i + 1, j, 2))dp[i + 1][j][2] += dp[i][j][2];
if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][2];
if(check(i, j + 1, 0))dp[i][j + 1][0] += dp[i][j][1];
if(check(i + 1, j, 2))dp[i + 1][j][2] += dp[i][j][1];
if(check(i + 1, j + 1, 1))dp[i + 1][j + 1][1] += dp[i][j][1];
}
}
int ret = dp[n][n][0];
ret += dp[n][n][1]; ret += dp[n][n][2];
cout << ret << "\n";
return 0;
}
mch님의 코드는 완탐입니다.
완탐과 DP의 차이는 메모이제이션의 여부입니다. 저는 dp라는 배열을 기반으로 그 이전의 경우의 수를 저장해두고 있다는 점이 차이점입니다.
int go(int y, int x, int curDir)
{
if (y == n && x == n) return 1;
int ret = 0;
int temp = continueIndex(curDir);
for (int i = 0; i < 3; ++i)
{
if (temp == i) continue;
int ny = y + dy[i];
int nx = x + dx[i];
if (ny<1 || nx<1 || ny >n || nx >n) continue;
if (a[ny][nx]) continue;
if (i == 1 && (a[ny][nx] || a[ny - 1][nx] || a[ny][nx - 1])) continue;
ret += go(ny, nx, i);
}
return ret;
}
mch님 코드는 메모이제이션도 없고 딱 완탐인데... 흐으음..
시간 많이 잡아먹긴하지만 신기하네요 ㅎ
그리고 시간복잡도가 3^16도 아닙니다.
격자판의 크기가 n x n이므로, 이동하는 것을 고려하면 -> 대각선으로 이동할 때 최소값인 2n-1입니다. 하지만, 실제로는 가로 또는 세로로만 이동하는 경로도 고려해야 하므로, 경로의 최대 길이는 2n보다 클 수 있습니다. 그래서 얼추... 3^32가 되는 것이죠.
이거 원래는 절대 안된다고 보시면 됩니다.
mch님이 처음에 생각하신게 맞고 -> 완탐 -> 시간복잡도상 불가능
but, 이 문제 자체의 시간초과상한선이 널널해서 그런 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
안녕하세요 mch님 ㅎㅎ
> 격자판의 크기가
nxn이므로, 이동하는 것을 고려하면 -> 대각선으로 이동할 때 최소값인2n-1입니다. 하지만, 실제로는 가로 또는 세로로만 이동하는 경로도 고려해야 하므로, 경로의 최대 길이는2n보다 클 수 있습니다. 그래서 얼추... 3^32가 되는 것이죠.>> 이부분 설명 수정하겠습니다...
최대 시간 복잡도는 3^(2n - 1) 이 됩니다.
이 문제를 봤을 때 어떠한 경로가 있을까? 라고 생각해보면 아래로 내려가는 경로밖에 없음을 알 수 있습니다. 위로 올라가지는 않죠.
세로 - 가로로 이동하게 되면 2n의 경로를 가지고
대각선으로만 이동하게 되면 n 의 경로를 가지는 것을 알 수 있습니다.
1.문제 처음 조건인 가로짜리 하나 놓아져있다.
2.선을 기반으로 파이프를 놓는게 아니라 격자안에다가 넣는다.
이런 것들은 일단 제외하고 말씀드릴게요.
이 경로에서 어떠한 방법으로 갈건지를 결정해야 하는 것이고 최대 3^2n이 되는 것이죠.
다만, 문제 조건을 보면 가로 -> 세로가 바로 안되기 때문에 가로 - 세로 안에는 대각선이 들어가야 하는 게 자명합니다. 그렇다고 하면 3^(n - 1) ~ 3^(2n - 1) 사이가 됩니다. 대각선 하나만 들어가는 경우는 3^(2n - 1)이 되겠죠. 즉, 최대 시간복잡도는 경로가 가장 긴 3^(2n - 1)이 됩니다.
그러나... 이 문제를 풀 때 이렇게 복잡하게 들어갈 필요는 없습니다.
각 격자당 상태값은 3개이기 때문에
3^(n*n)이 됩니다.
하지만 이를 DP로 만들게 되면
n x n x 3이 되는 것이죠.
해당 정점이 어떻게 끝나느냐 : 가로 또는 세로, 대각선 이러한 상태값을 중심으로 그 상태값에서 경우의 수 + 해가면서 결과를 만들어내는 것이니까요.
제가 답변을 잘 드렸어야 했는데 저도 좀 착각해가지고... 혼란을 드려 죄송합니다.
또 질문있으시면 질문주세요 ㅎㅎ
감사합니다.