Baekjoon 5573 산책

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

소스결과 9816 KB / 68 ms

언어 C++ 17

출처 Baekjoon

분류 다이나믹 프로그래밍, 조합론

 

설명

시뮬레이션으로 돌려도 될꺼 같지만 실제로 돌리면 안되는 문제

0,0에서 출발하여 오른쪽/아래 로 움직일 때 k 번 산책때 어디서 끝나는지 출력하여라.

 

처음에는 1천만번이면 될 줄 알고 돌렸지만 그럴리가 없었다.

 

keyPoint는 처음 상태를 기준으로 홀수 / 짝수번 접근 후를 예측하는 것이다.

특정 위치에 k 번 접근 후에 아래/오른쪽으로 움직이는 경우의 수가 특정해진다.

 

알고리즘

1. 초기 상태를 입력 받는다.

2. 0,0 위치는 n번 접근한다. dp[0][0]을 n으로 초기화 해주낟.

3. i, j위치를 기준으로 i, j+1 / i + 1, j위치를 (dp[i][j] + 1) / 2 or dp[i][j] - ((dp[i][j] + 1) / 2)로 초기화한다.

4. 모든 위치에 대해서 진행 후 기존 배열에 dp배열을 추가해준다.

5. 시뮬레이션을 진행하여 결과값을 출력한다.

 

소스코드

 

#include <iostream>

using namespace std;

const int MAX = 1000;

int board[MAX + 1][MAX + 1];
int dp[MAX + 1][MAX + 1];

const int posX[] = { 1, 0 };
const int posY[] = { 0, 1 };

const int _max(const int a, const int b) { return a ^ ((a^b) & -(a < b)); }

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h, w, n; cin >> h >> w >> n;

	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			cin >> board[i][j];

	dp[0][0] = n - 1;

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

	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			board[i][j] += dp[i][j];
		}
	}

	int resX = 0, resY = 0;
	while (0 <= resX && resX < h && 0 <= resY && resY < w) {
		int move = board[resX][resY] & 1;
		resX += posX[move]; resY += posY[move];
	}

	cout << resX + 1 << ' ' << resY + 1;

	return 0;
}