[백준]5573 산책 #dp

1. 풀이

(1) N번째의 상태를 확인하기 위해 N-1번수행한 후의 맵을 구현한다.

(2) d[i][j] : 현재 맵의 상태. 0이면 아래, 1이면 오른쪽

(3) d[i][j]에 N번 존재하면, d[i+1][j], d[i][j+1]에 N/2번 존재한다.

이때 d[i][j]가 아래이면 d[i+1][j]가 추가로1이 더해지고, 오른쪽이면 d[i][j+1]가 추가로1 더해진다.

(4) 최종맵은 홀수이면 오른쪽(1)이고, 짝수이면 아래(0)이므로 2로 모듈러연산을 해준다.

(5) 최종답을 구하기 위해 N번째 산책을 시작한다.

​

2. 소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int d[1002][1002];
int map[1002][1002];

int main() {
	int H, W, N;
	cin >> H >> W >> N;

	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			cin >> map[i][j];
		}
	}

	// n-1산책 후 상태를 만든다.
	d[1][1] = N - 1;
	for (int i = 1; i <= H; i++) {
		for (int j = 1; j <= W; j++) {
			/*
			if (d[i][j] == 0) {
				continue;
			}
			*/

			d[i + 1][j] += d[i][j] / 2;
			d[i][j + 1] += d[i][j] / 2;

			if (d[i][j] % 2 == 1) {
				if (map[i][j] == 1) {
					d[i][j + 1]++;
				}
				else {
					d[i + 1][j]++;
				}
			}
			map[i][j] = (map[i][j] + d[i][j]) % 2;
		}
	}

	//N번째 산책 시작
	int r = 1;
	int c = 1;
	while (1) {
		if (map[r][c] == 1) {
			c++;
		}
		else {
			r++;
		}
		if (c == W + 1 or r == H + 1) {
			break;
		}
	}
	cout << r << " " << c;



	return 0;
}