-

DFS로 해결가능 한 문제이다. 하지만 다른 분들이 푼 방식을 보니 DP를 사용하였더라. DFS로 단순히 탐색을해서 푼것보다 분명 DP를 사용해 푸는것이 시간적인 면에서 훨씬 효율적일 거란 생각이 든다. 우선 내가 푼 방식은 1일째부터 차례대로 dfs로 탐색을 해준다. 표에 있는 예제대로 진행한다면, 1일에 일을 했따면 4일부터 가능하다. 4일에 일을 할 수 있는지 판단하고 다시 dfs로 진행한다. 이처럼 매번 해당 일이 N+1의 마감일을 넘지 않는지 확인해 준다. 1일부터 시작했다면 2일부터 시작을 또 해줘야한다. 그렇게 3,4,5,6,7일을 "시작으로" 탐색을 시작한다. 왜냐하면 저 예제에서는 1일부터 하는 것이 최적의 답이겠지만, 다른 경우가 충분히 있을 수 있기 때문이다 !! dfs에서 V[i]를..

설마 모든 좌표에 대해서 3개의 벽을 세운뒤 BFS로 문제가 해결될 줄 몰랐다. 맵의 크기가 작기 때문에 가능했다. DFS를 보통 x,y,len 이런식의 파라미터를 넣는게 익숙하다 보니 습관적으로 문제를 정확히 분석하기 보다는 습관대로 파라미터를 만들어 놓고 시작하는데 좋지 않은 습관인듯하다. 복습할 때 DFS 활용 방식을 꼭 눈여겨 보자. 코드: #include #include #include using namespace std;int N, M;int map[9][9];int map2[9][9]; int px[4] = { -1, 0, 1, 0 };int py[4] = { 0, -1, 0, 1 }; // up left down rightint cnt;int num_1;int num_2;int ans;st..

처음에 그냥 DFS로만 풀었다가 시간초과가 났다. N이 100정도 되기 때문에 DFS로는 시간 초과가 해결이 안된다. 따라서 DP를 적용하여 풀어야만 한다. DP[x][y] 를 -1로 초기화 해두고, 방문하는 좌표에 0을 넣어 준다.(그래야지 방문했는지 안했는지 알 수 있다.) DP[x][y]는 (x,y)를 지나서 (n,n) 까지 도달 할 수 있는 경로를 저장해준다고 생각하면 된다. 그렇기 때문에 다른 경로를 통해 (x,y)를 다시 방문하였을 때는 더 탐색하지 않고 해당 값만 return 해주면 된다! 그렇게 되면 DP[0][0]에는 (0,0) ~ (n,n) 까지의 경로가 저장되게 된다. 코드: #include using namespace std;typedef long long lld;int N;int ..

단순 무식한 방법이 먹힌듯 하다. map을 초기화 할 때 1이 입력되는 좌표들은 모두 Q에 push ! 큐를 팝하면서 연결되어있는 부분들을 탐색 ! 그 과정에서 집의 수를 세어준다 ! 코드: #include #include #include #include using namespace std; int N;int D[26][26];int visited[26][26]; int px[4] = { 1, 0, -1, 0 }; // down right up leftint py[4] = { 0, 1, 0, -1 };struct pos{int x;int y;};int cnt;int total;queue Q; char tmp[26];void dfs(int x, int y){ if (visited[x][y] == 1) re..

메모리 초과 난 코드. 애초에 모든 점들을 방문하는건 무리! dfs에서 스택을 엄청나게 잡아먹기 때문에 2500 2500 5000 이런 식으로 입력하면 메모리가 날라간다. #include #include //#includeusing namespace std; int map[5001][5001];int visited[5001][5001];int R[5001]; int px[4] = { 1, 0, -1, 0 }; // down right up leftint py[4] = { 0, 1, 0, -1 }; bool flag = false;struct pos{int x;int y;};pos arr[5001];queue Q;int cnt;int index = 0;int N;void F(int xt, int yt, i..

S/W 엔지니어를 포기할 까 고민하게 만든 문제였다. 결국 많이 풀어봐야 할 것 같다,, DP문제를 풀 때, 습관적? 고정관념적으로 DP[n] = DP[n-1] + DP[n-2] 처럼 매우 1차원적으로 점진적으로 값이 (오른쪽으로) 쌓여간다는 생각을 하게된다. 이렇게 1차원 적으로 DP문제를 접근하면 절~~~ 대로 풀 수 없는 문제인 것 같다. 우선 이 문제를 풀기 위한 핵심은 1. 파일이 합쳐 지는 원리(계산)2. DP 점화식 세우기 1번 같은 경우 문제를 "정확히" 분석하지 않고 냅다 코딩부터 하니... 2번을 올바르게 세웠더라도 이 문제는 시간초과로 틀렸을 것이다. 여기서 가장 중요한 사실은 인접한 경우에만 합칠 수 있다는 것! 1~2개는 굳이 점화식이 필요없이 계산이 가능하다. 하지만 3장 부터가..

계단오르기 문제와 비슷한 DP 문제이다. 계단 오르기와 비슷하게 기준을 만들어야 한다. 기준없이 경우를 고려하면 점화식을 세우기 힘들다. 포도주 잔의 갯수를 1 부터 시작하여 차례대로 dp를 만들어 나간다. 1잔일 경우 당연히 dp[1] = a[1]; 이다. dp[2] = a[1] + a[2]; 가 된다. 3잔 부터는 기준이 필요.(3잔 이후로는 같은 원리가 적용됨) *연속된 세잔은 불가능 하다. 1. 마지막 잔을 마시지 않을 경우 dp[n] = dp[n-1]; 2. 마지막 잔을 마시는데 첫 번째 잔일 경우. dp[n] = dp[n-2] + a[n]; 3. 마지막 잔을 마시는데 두 번째 잔일 경우. dp[n] = dp[n-3] + a[n-1] + a[n]; 이렇게 경우를 나누어 주면 문제는 굉장히 쉽게 ..

처음 짜서 런타임에러 + 논리적 오류가 발생한 코드 #include #include using namespace std; int D[1001];int XY[1001][1001];int DP[1001]; int main(){ int T = 0, N = 1, K = 1, X, Y, W; cin >> T; while (T--){int ans = 0;cin >> N >> K;for (int i = 1; i > D[i];} for (int i = 1; i > X >> Y;XY[X][Y] = 1;}cin >> W; DP[1] = D[1];for (int i = 1; i N >> K; for (int j = 1; j > D[j];for (int j = 0; j < K; j++) {int x, y;//scanf("%d..