-

처음에 그냥 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..

브루트포스로 풀릴것 같은데 왠지 시관초과가 날 것 같다. 꼭 다시 재귀방법으로 풀어보기로. 변수 정의를 잘 해야겠다. D[x] 를 "x를 1로 만드는데 필요한 최소한의 연산 횟수" 라고 정의한다면 문제가 쉬워진다. 코드:#include using namespace std; int D[1000001]; int main(){int X;cin >> X; D[1] = 0;D[2] = D[3] = 1;int temp = 0;for (int i = 4; i

점화식으로 바로 접근해서 헷갈리는 부분이 많았다. D[n] = Max(D[n-2),D(n-1) + S(n) 이런 형식을 가지고만 생각하면 풀기 너무 어려워진다. 경우의 수를 나누어야 한다. 제일 마지막 계단은 무조건 밟아야 하는 것과 세번 연속 오를 수 없다는 것을 기준으로 경우를 나눠야 한다. 두가지 경우로 나누어 생각. 즉, 점화식을 세울 때 O X O O --> D[n-3] + S[n-1] + S[n] // 전전전칸까의 최대값 + 전계단 + 마지막 계단 ? O X O --> D[n-2] + S[n] // 전전칸까지의 최대값 + 마지막 계단 코드: #include /*계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수..