백준 5573 산책 혼내주기

 

 

 

어이없게 홀짝으로 해당 칸을 몇번 방문했는지 계산하는 것 까지 다 해놓고, N번째를 도착점을 어떻게 계산할지 몰라서 찾아봤다...

(x, y)번째 칸은 (x-1, y)칸과 (x, y+1)칸의 방문 횟수의 합인걸 이용해 dp로 n-1번 산책했을 때의 상태를 저장해놓고 n번째는 경로에 맞게 따라가면 된다.

dp문제를 별로 안좋아하는데 이번 문제는 뭔가 재미있었다. 나 의외로 dp를 좋아할지도??...

 

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(v) v.begin(), v.end()

int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

int cache[1005][1005];
bool arr[1005][1005];
int n, m, k;

void input() {
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            cin >> arr[i][j];
        }
    }
}

int main() {
    fastio;
    input();
    
    cache[1][1] = k-1;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            if(i == 1 && j == 1) continue;

            int left, up;
            // 오
            if(arr[i][j-1]) {
                if(cache[i][j-1] & 1) left = cache[i][j-1]/2+1;
                else left = cache[i][j-1]/2;
            }
            else left = cache[i][j-1]/2;

            // 아
            if(!arr[i-1][j]) {
                if(cache[i-1][j] & 1) up = cache[i-1][j]/2+1;
                else up = cache[i-1][j]/2;
            }
            else up = cache[i-1][j]/2;

            cache[i][j] = left + up;
        }
    }

    int x = 1, y = 1;
    while(x <= n && y <= m) {
        // inv
        if(cache[x][y] & 1) {
            // 오
            if(arr[x][y]) x++;
            else y++;
        }
        else {
            if(arr[x][y]) y++;
            else x++;
        }   
    }
    cout << x << " " << y;
}