[BOJ백준] 5574 산책

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

5573번: 산책

---

문제해설

H와 W의 입력자체가 1000까지 들어오지만, N이 10^7까지 들어오기 때문에,

일반적인 시뮬레이션으로는 해결 할 수없어 보입니다.

총 N번 산책을 했을 때, 어떤 교차점에대해서 몇번 지나게 되는가를 미리 계산하면 됩니다.

(1,1) 정점은 N번 산책을 할 경우 N번 지나게 될 것입니다.

(1,2)는 대략적으로 N/2

(2,1)도 대략적으로 N/2

...

이런식으로 dp 테이블을 생성해 나아가면 됩니다.

 

< 예시 >

W = 1, H = 1 인 케이스에서 N 이 주어졌다고 생각해봅시다.

N번 산책동안 1,1를 N번 지나게됨으로

N번 산책일때 오른쪽으로 가는가, 왼쪽으로 가는가만 계산하면 될텐데

첫 입력에서 (오른쪽)이 주어졌다면

짝수번 방문할 경우는 (2,1)

홀수번 방문할 경우는(1,2)

에 도착하게됩니다.

 

W = 2, H = 2인 케이스에서 N이 주어졌다고 생각해봅시다.

N이만약 짝수라면

dp[1][1] = N번

dp[2][1] = dp[1][1]/2

dp[1][2] = dp[1][1]/2

dp[2][2] = dp[1][2]/2 + dp[2][1]/2

가 될 것입니다. 

 

위의 같은케이스에서 N이홀 수라면 

처음 입력에 따라서 오른쪽이나 아래쪽에 1이 더큰 숫자가 들어가게 될 것입니다.

---

 DP 테이블을 완성한뒤에

mod2 연산을 하게 되었을때 dp 테이블에 남은 숫자가 곧

방향을 알려줄 것이고

DFS를 통해 결과를 구 할 수 있습니다.

---

전체코드

#include <iostream>
using namespace std;

int arr[1001][1001];
int dp[1001][1001];
int R, C, N;
pair<int, int> ans;

void DFS(int r, int c) {
	if (r >= R || c >= C) {
		ans = { r,c };
		return;
	}
	if (arr[r][c] == 1) {
		if (dp[r][c] == 1) 
			DFS(r, c + 1);
		else 
			DFS(r + 1, c);
	}
	else {
		if (dp[r][c] == 1)
			DFS(r+1, c);
		else 
			DFS(r, c+1);
	}
}


int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> R >> C >> N;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cin >> arr[i][j];
		}
	}

	dp[0][0] = N;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (arr[i][j] == 1) {
				dp[i+1][j] += dp[i][j] / 2;
				dp[i][j+1] += (dp[i][j] % 2 == 0) ? dp[i][j] / 2 : dp[i][j] / 2 + 1;
			}
			else {
				dp[i+1][j] += (dp[i][j] % 2 == 0) ? dp[i][j] / 2 : dp[i][j] / 2 + 1;
				dp[i][j + 1] += dp[i][j] / 2;
			}
		}
	}

	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			dp[i][j] %= 2;
		}
	}
	DFS(0, 0);
	cout << ++ans.first  << " " << ++ans.second << "\n";
}