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](초기방향이 오른쪽))(아래로 갈 때) . 이를 구하고 답을 ..
2021.11.16