백준 11048번 - 이동하기

www.acmicpc.net/problem/11048

11048번: 이동하기

dp 문제이다.

요즘 dp를 많이 풀어보고 싶어서 풀어봤는데

처음 봤을때 dp가 아닌줄 알았다.

 

누가봐도 bfs 문제 같아서 에라 모르겠다 하고 bfs로 풀다 보니 뭔가 이상..

 

bfs와 dp를 섞어서 풀다보니 뭔가 쎄~ 했다.

 

일단 예제랑 반례들 답이 잘 나오길래 제출하긴 했는데 메모리초과!!

 

역시 느낌이 중요하다니까

 

잠시 고민해봤는데 아무래도 bfs를 사용할 때 queue에 너무 많은 데이터가 들어가서 메모리 초과가 나는 것 같다.

 

그리고 나서 연습장에 끄적여 봤는데 

생각보다 너무 간단한 문제였네..?

 

내가 사용한 해결방법은 다음과 같다.

 

첫 번째 열과 첫 번째 행을 제외한 나머지 칸들은 모두 자신의 왼쪽 칸과 위쪽 칸에만 영향을 받는다!

 

 

이 문제에서 각 칸에서 오른쪽, 아래쪽, 오른쪽 대각선 아래 방향, 이 3가지 방향으로만 움직일 수 있다는 조건이 Hint였다!

 

앞에서 뭐한거지.. 이렇게 생각한 뒤에 코드를 짜는건 간단했다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int arr[1004][1004];
int dp[1004][1004];
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    memset(dp, 0, sizeof(dp));
    int n, m;
    // 입력
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
        }
    }
    // dp 구하기
    dp[0][0] = arr[0][0];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (i == 0 && j == 0) continue;  // [0][0]은 이미 넣어줬으니까 
            if (i == 0) dp[i][j] = dp[i][j - 1] + arr[i][j];  // 첫 번째 행은 자신의 왼쪽 칸에만 영향을 받음
            else if (j == 0) dp[i][j] = dp[i - 1][j] + arr[i][j]; // 첫 번째 열은 자신의 위쪽 칸에만 영향을 받음
            else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + arr[i][j]; // 나머지 칸들은 각각 왼쪽 칸과 위쪽 칸에 영향을 받음
        }
    }
    cout << dp[n - 1][m - 1] << "\n";

 

dp는 차분히 생각해 보고 푸는게 더 빨리 풀 수 있는것 같다.

 

bfs처럼 무작정 구현하면서 맞춰나가는 방식으로 풀어보니 답도 없다