BOJ 5573 : 산책

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

여학 때 풀지 못해서 업솔빙을 한 문제이다.

 

우리는 K번 후 각 위치에 대해 몇 번 방문했느냐에 따라 다음 방향이 달라짐을 관찰 할 수 있다. 

이를 dp로 구하면 된다.

dp[i][j] = (i,j)를 몇 번 지나갔는가?

 

dp[1][1]은 초기 위치에서 몇 번 지나갔는가를 물으므로 k-1일테고, 식은

dp[i+1][j] = dp[i][j]/2 + (dp[i][j]%2(i,j에서의 초기 방향이랑 다른가) & !a[i][j](초기방향이 아래))(오른쪽으로 갈 때)

dp[i][j+1] = dp[i][j]/2 + (dp[i][j]%2(i,j에서의 초기 방향이랑 다른가) & a[i][j](초기방향이 오른쪽))(아래로 갈 때)

.

이를 구하고 답을 dp테이블로 추적해서 구하면 된다.

 

괜찮은 문제라고 생각한다. 이렇게 접근하는 것도 처음이어서 좀 기억에 남기도 했다.

코드