5573 산책

https://www.acmicpc.net/problem/5573

5573번: 산책

 

d[i][j] = n-1번 산책한 후 교차로 (i,j)의 방문 횟수

 

i) d[i][j] = 짝수이면 초기 방향 상태가 그대로 유지된다

ii) d[i][j] = 홀수이면 초기 방향 상태와 방향이 다르다

 

위의 dp 정의를 통해 점화식을 찾아보자. 시작점은 무조건 지나므로 초기값 d[1][1] = n-1이다.

오른쪽, 아래쪽으로 가는 경우인 d[i][j+1],d[i+1][j]는 지나갈 때 마다 방향이 매번 바뀌므로 일단 그 전 위치인 d[i][j]에서 2로 나눈 값이 들어간다. 여기서 d[i][j]가 홀수인 경우에 방향까지 고려해서 +1를 해줄 것인지 결정한다.

 

d[i][j+1] = d[i][j]/2 + (a[i][j] = 오른쪽 and d[i][j] = 홀수)

d[i+1][j] = d[i][j]/2 + (a[i][j] = 아래 and d[i][j] = 홀수)

 

dp 테이블을 완성했으면 이를 이용해서 (1,1)부터 가장자리 위치까지 갈때까지 위치를 옮겨보면 된다.

 

#include <cstdio>

int h,w,n,x,y,a[1005][1005],d[1005][1005];

int main()
{
    scanf("%d %d %d",&h,&w,&n);
    for(int i=1;i<=h;i++)
        for(int j=1;j<=w;j++)
            scanf("%d",&a[i][j]);
    d[1][1]=n-1;
    for(int i=1;i<=h;i++)
    {
        for(int j=1;j<=w;j++)
        {
            d[i][j+1]+=d[i][j]/2+(a[i][j]==1 && d[i][j]%2==1);
            d[i+1][j]+=d[i][j]/2+(a[i][j]==0 && d[i][j]%2==1);
        }
    }
    x=y=1;
    while(1)
    {
        if(d[x][y]%2==0)
        {
            if(a[x][y]==0)
                x++;
            else
                y++;
        }
        else
        {
            if(a[x][y]==0)
                y++;
            else
                x++;
        }
        if(x==h+1 || y==w+1)
        {
            printf("%d %d",x,y);
            break;
        }
    }
    return 0;
}