[PS] 백준 5573번: 산책

|

문제

내가 이해한 문제 내용

$N$번의 산책을 하는데 1이면 오른쪽으로 0이면 아래쪽으로 이동한다. $H\times W$ 크기의 산책로가 주어질 때 $N$번째 산책로의 도착행과 열을 구하시오.

접근 방식

  • 처음엔 계속해서 패턴을 찾다가 답이 없다는 것을 깨달았다.
  • 인터넷에 답변도 없어서 질문란에 있는 힌트를 보고 간신히 해결했다.
  • 3차원 DP 점화식을 통해 해결할 수 있다.
    • DP[i][j][1] i행 j열에서 오른쪽으로 이동하는 횟수
    • DP[i][j][0] i행 j열에서 아래쪽으로 이동하는 횟수
  • 2로 나눈 몫과 나머지를 이용하는 것이 핵심이며 현재 지점이 1이냐 0이냐에 따라 그 횟수가 더 추가된다.

어려웠던 점 & 배운 점

  • 부스터급의 어려움을 지닌 문제였다.
  • 처음부터 DP를 고려하지 않고 제외한 실수가 너무 크다.
  • 이런 타입의 문제는 DP 유형이 많다는 것을 꼭 알아두자.
  • DP의 점화식을 방문한 횟수로 두는 것이 DFS+DP 타입의 문제에서도 나오니 기억하자.

시간복잡도

  • $O(HW)$

코드

#include <cstdio>

int path[1005][1005];
int dp[1005][1005][2];
int n,h,w;

int main(void)
{
    scanf("%d%d%d",&h,&w,&n);
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            scanf("%d",&path[i][j]);
        }
    }

    dp[1][1][1] = path[1][1] ? (n-1)/2 + (n-1)%2 : (n-1)/2;
    dp[1][1][0] = !path[1][1] ? (n-1)/2 + (n-1)%2 : (n-1)/2;

    for(int i=2; i<=h; i++){
        dp[i][1][1] = path[i][1] ? dp[i-1][1][0]/2 + dp[i-1][1][0]%2 : dp[i-1][1][0]/2;
        dp[i][1][0] = !path[i][1] ? dp[i-1][1][0]/2 + dp[i-1][1][0]%2 : dp[i-1][1][0]/2;
    }
    for(int i=2; i<=w; i++){
        dp[1][i][1] = path[1][i] ? dp[1][i-1][1]/2 + dp[1][i-1][1]%2 : dp[1][i-1][1]/2;
        dp[1][i][0] = !path[1][i] ? dp[1][i-1][1]/2 + dp[1][i-1][1]%2 : dp[1][i-1][1]/2;
    }

    for(int i=2; i<=h; i++){
        for(int j=2; j<=w; j++){
            int in = dp[i-1][j][0] + dp[i][j-1][1];
            dp[i][j][1] = path[i][j] ? in/2 + in%2 : in/2;
            dp[i][j][0] = !path[i][j] ? in/2 + in%2 : in/2;
        }
    }

    int r = 1, c = 1;
    while(r<=h && c<=w) {
        int visit = dp[r][c][0]+dp[r][c][1];
        path[r][c] = visit%2==0 ? path[r][c] : !path[r][c];
        path[r][c] ? c++ : r++;
    }

    printf("%d %d",r,c);

    return 0;
}