5573번: 산책
첫째 줄에 H, W, N이 주어진다. (1 ≤ H,W ≤ 1000, 1 ≤ N ≤ 107) 둘째 줄부터 H개 줄에는 W개 정수가 주어진다. 이 정수는 상근이가 교차로에 써 놓은 문자의 정보이다. 0은 아래쪽을 의미하는 '아', 1은
www.acmicpc.net
1000 * 1000에 10000000번 산책을 하기때문에 시뮬레이션으로 접근하다가는 무조건 시간초과 뜹니다.
저는 방향정보를 dp를 이용하여 N - 1번까지 산책한 이후의 경로를 만들어 놓고 마지막 한 번 산책하는 방식으로 하였습니다.
dp에는 N - 1번의 산책동안 (x, y)에 몇 번 지나갔는지 표시하는데 사용하였습니다.
여기서 문제에서 산책하는 규칙이 있습니다.
0은 아래쪽, 1은 오른쪽 방향으로 가며 한 번 어떤 방향으로 가면 그 다음번 산책에서는 반드시 다른 방향으로 이동하게 되어있습니다.
따라서 dp[x][y]는 dp[x-1][y]에서 방문한 횟수의 1/2 + dp[x][y-1]에서 방문한 횟수의 1/2를 한 값입니다.
여기서 추가해야할 것이 dp[x-1][y], dp[x][y-1]이 홀수일 때 방향에 따라서도 방문횟수가 추가될 수 있습니다.
(x-1, y) 즉, 위쪽 방향에서 밑쪽으로 지나가려면 경로는 아래쪽 방향이 되어있어야합니다.
(x, y-1) 즉, 왼쪽 방향에서 오른쪽으로 지나가려면 경로는 오른쪽 방향이 되어있어야합니다.
위의 두가지를 추가하기 위해 처음에 받은 list[x-1][y], list[x][y-1]을 확인해야합니다.
(x-1, y)의 경우 처음 방향인 list[x-1][y]이 0이면 홀수일 때 1을 추가해줍니다.
(x, y-1)의 경우 처음 방향인 list[x][y-1]이 1이면 짝수일 때 1을 추가해줍니다.
이렇게 dp를 다 구하고 나면 이를 이용하여 산책경로를 모두 바꿔야합니다.
dp[x][y]가 짝수인 위치는 방향을 바꿀 필요 없고, 홀수인 위치에만 방향을 바꿔줍니다.
마지막으로 x=1, y=1에서부터 맵밖으로 산책을 즐기시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][] = new int[1001][1001];
static int H, W, N;
static void solve() {
int x = 1;
int y = 1;
while (true) {
if (list[x][y] == 1)
y++;
else
x++;
if (x > H || y > W)
break;
}
System.out.println(x + " " + y);
}
static void func() {
int dp[][] = new int[H + 1][W + 1];
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (i == 1 && j == 1) {
dp[i][j] = N - 1;
continue;
}
dp[i][j] = dp[i - 1][j] / 2 + dp[i][j - 1] / 2;
if (dp[i - 1][j] % 2 == 1 && list[i - 1][j] == 0)
dp[i][j]++;
if (dp[i][j - 1] % 2 == 1 && list[i][j - 1] == 1)
dp[i][j]++;
}
}
for (int i = 1; i <= H; i++) {
for (int j = 1; j <= W; j++) {
if (dp[i][j] % 2 == 0)
continue;
list[i][j] = 1 - list[i][j];
}
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
H = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
N = Integer.parseInt(st.nextToken());
for (int i = 1; i <= H; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 1; j <= W; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
func();
solve();
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1010 다리 놓기 (0) | 2021.02.05 |
|---|---|
| boj 5557 1학년 (0) | 2021.02.05 |
| boj 17528 Two Machines (0) | 2021.01.28 |
| boj 9657 돌 게임 3 (0) | 2021.01.27 |
| boj 2096 내려가기 (0) | 2021.01.22 |