[BOJ | 백준] 5573번: 산책

by Kimcoding on 2020-04-17 03:34

in BOJ

문제 설명

BOJ 5573

각 좌표마다 초기에 방향이 정해져있고, 한 번 지나갈 때마다 방향이 바뀝니다.

이럴 때 N번째 산책을 하였을 때 도착하는 좌표를 구하는 문제입니다.

풀이

마음 편하게 시뮬레이션을 하고 싶지만 N이 최대 1000만이므로 시간 초과입니다

N-1의 산책을 마친 후 교차로의 정보를 알 수 있다면 한 번의 시뮬레이션을 통해 답을 구할 수 있습니다.

교차로 (i,j)에 K번 방문을 했습니다.

K가 홀수라면 방향이 다를 것이고, 짝수라면 방향이 처음과 같습니다.

한 번 지나갈 때마다 방향이 달라지기 때문에 (i + 1,j), (i, j + 1)으로 갈 경우는 K/2입니다.

K가 홀수라면 예외처리로 원래 방향에 1을 더해줘야 합니다.

DP테이블을

DP[1][1] = N - 1

DP[i][j+1] = DP[i]][j] / 2 + (초기 방향 == 오른쪽 && DP[i][j] == 홀수)

DP[i+1][j] = DP[i]][j] / 2 + (초기 방향 == 아래 && DP[i][j] == 홀수)

이렇게 저장하게 된다면 N-1번 산책했을 때 교차로의 방향을 알 수 있습니다.

방향을 구했으니 (1,1)부터 DP[i][j]가 홀수라면 초기 방향과 다르고 짝수라면 초기 방향과 같게 산책을 하다보면 답을 구할 수 있습니다.

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(a,b,c) for(int a = (b); a <= (c); a++)
using namespace std;

int main() {
	FIO;
	int n, m, k;
	cin >> n >> m >> k;
	int dp[1005][1005] = {}, map[1005][1005];
	FOR(i, 1, n) FOR(j, 1, m) cin >> map[i][j];

	dp[1][1] = k - 1;
	FOR(i, 1, n) FOR(j, 1, m) {
		int d = dp[i][j];
		dp[i][j + 1] += (d / 2 + (d & 1) * map[i][j]);
		dp[i + 1][j] += (d / 2 + (d & 1) * !map[i][j]);
	}

	int r = 1, c = 1;
	while (r <= n && c <= m) {
		if ((dp[r][c] & 1) ^ map[r][c]) c++;
		else r++;
	}
	
	cout << r << ' ' << c << '\n';
	return 0;
}