문제
마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.
토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.
토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.
토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.
토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.
입력
첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.
출력
격자의 밖으로 나간 모래의 양을 출력한다.
제한
- 3 ≤ N ≤ 499
- N은 홀수
- 0 ≤ A[r][c] ≤ 1,000
- 가운데 칸에 있는 모래의 양은 0
예제 입력 1
5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0
예제 출력 1
10
예제 입력 2
5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0
예제 출력 2
85
예제 입력 3
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
예제 출력 3
139
예제 입력 4
5
100 200 300 400 200
300 243 432 334 555
999 111 0 999 333
888 777 222 333 900
100 200 300 400 500
예제 출력 4
7501
예제 입력 5
5
0 0 100 0 0
0 0 100 0 0
0 0 0 0 0
0 0 100 0 0
0 0 100 0 0
예제 출력 5
283
예제 입력 6
9
193 483 223 482 858 274 847 283 748
484 273 585 868 271 444 584 293 858
828 384 382 818 347 858 293 999 727
818 384 727 373 636 141 234 589 991
913 564 555 827 0 999 123 123 123
321 321 321 983 982 981 983 980 990
908 105 270 173 147 148 850 992 113
943 923 982 981 223 131 222 913 562
752 572 719 590 551 179 141 137 73122961
풀이
이동하는 경로만 간단하게 계산하면 쉬운 문제이다.
대충 이동경로를 생각해보자.
처음에는
N = 5 인 맵을 생각해보자
← 1번, ↓ 1번
그 다음에는
→ 2번, ↑ 2번
그 다음에는
← 3번, ↓ 3번
그 다음에는
→ 4번, ↑ 4번 ← 4번 끝
이정도 쓰면 눈치 챌듯? 할거같네요. 방향은 반시계로 돌아가며, 1, 2, 3 이 두번 반복, 마지막 N-1번 이동시에는 연속3번 이동
이 규칙을 이해하면된다.
그리고 먼지 뿌리는건 현재 방향에서 -1, +1 방향으로 먼지를 뿌리고 남은 것을 알파에 뿌린다.
이떄 알파에 들어갈 먼지를 계산할때 유의 해야한다..
알파에 들어갈 먼지양을 계산시 int(이동하는 먼지양 * 0.01) 필수다. int *******
함수 리스트
void init(); // ios::~~`
void input(); // inpurt
void Move_Tornado(); // 토네이도를 계산하기 시작하는 함수
void move(); // 이동하는 것을 계산
void dust(); // 먼지가 퍼지는 것을 계산
bool check_map_range(int& next_x, int& next_y); // 맵 범위가 맞는지 계산
코드는 다음과 같다.
|
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
#include <iostream>
#include <iomanip>
#define MAX 1000+1
using namespace std;
int N;
int A[MAX][MAX];
// 0 1 2 3
// 왼쪽 아래쪽 오른쪽 위쪽
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
int Tornado_x; int Tornado_y;
int prev_x; int prev_y;
int dir = 0; int index = 1; int total = 0;
void init();
void input();
void Move_Tornado();
void move();
void dust();
bool check_map_range(int& next_x, int& next_y);
int main() {
init();
input();
Move_Tornado();
}
void init() {
ios::sync_with_stdio(false);
cin.tie(0);
}
void input() {
cin >> N;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> A[i][j];
total += A[i][j];
}
}
}
void Move_Tornado() {
Tornado_x = N / 2 + 1;
Tornado_y = N / 2 + 1;
dir = 0;
index = 1;
A[Tornado_x][Tornado_y] = 0;
while (Tornado_x != 1 || Tornado_y != 1) {
if (index == N - 1) {
move();
move();
move();
}
else {
move();
move();
index++;
}
}
int total_temp = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
total_temp += A[i][j];
}
}
cout << total - total_temp;
}
void move() {
for (int i = 0; i < index; i++) {
prev_x = Tornado_x;
prev_y = Tornado_y;
Tornado_x += dx[dir];
Tornado_y += dy[dir];
dust();
}
dir += 1;
if (dir == 4)
dir = 0;
}
void dust() {
// 0 1 2 3
// 왼쪽 아래쪽 오른쪽 위쪽
// x -> y -> a 순으로 먼지 날릴 양 계산
// dir 방향에서 +1, -1 방향으로 퍼진다
int dir_dust[2] = { dir + 1,dir - 1 };
int dust_total = A[Tornado_x][Tornado_y];
int alpah_dust = dust_total;
A[Tornado_x][Tornado_y] = 0;
int alpha_x = Tornado_x + dx[dir];
int alpha_y = Tornado_y + dy[dir];
if (dir_dust[0] == 4)
dir_dust[0] = 0;
if (dir_dust[1] == -1)
dir_dust[1] = 3;
for (int i = 0; i < 2; i++) {
int next_x = prev_x + dx[dir_dust[i]];
int next_y = prev_y + dy[dir_dust[i]];
if (check_map_range(next_x, next_y) == true) {
A[next_x][next_y] += dust_total * 0.01;
}
alpah_dust -= int(dust_total * 0.01);
}
for (int i = 0; i < 2; i++) {
int next_x = Tornado_x;
int next_y = Tornado_y;
for (int j = 0; j < 2; j++) {
next_x += dx[dir_dust[i]];
next_y += dy[dir_dust[i]];
if (check_map_range(next_x, next_y) == true) {
if (j == 0) {
A[next_x][next_y] += dust_total * 0.07;
alpah_dust -= int(dust_total * 0.07);
}
else if (j == 1) {
A[next_x][next_y] += dust_total * 0.02;
alpah_dust -= int(dust_total * 0.02);
}
}
else {
if (j == 0) {
alpah_dust -= int(dust_total * 0.07);
}
else if (j == 1) {
alpah_dust -= int(dust_total * 0.02);
}
}
}
}
for (int i = 0; i < 2; i++) {
int next_x = alpha_x + dx[dir_dust[i]];
int next_y = alpha_y + dy[dir_dust[i]];
if (check_map_range(next_x, next_y) == true) {
A[next_x][next_y] += dust_total * 0.1;
}
alpah_dust -= int(dust_total * 0.1);
}
int next_x = alpha_x + dx[dir];
int next_y = alpha_y + dy[dir];
if (check_map_range(next_x, next_y) == true) {
A[next_x][next_y] += dust_total * 0.05;
}
alpah_dust -= int(dust_total * 0.05);
if (check_map_range(alpha_x, alpha_y) == true) {
A[alpha_x][alpha_y] += alpah_dust;
}
}
bool check_map_range(int& next_x, int& next_y){
if (next_x >= 1 && next_x <= N && next_y >= 1 && next_y <= N) {
return true;
}
return false;
}
|
cs |
코드를 줄이면 120? 까지도 줄일 수 있을거같지만 귀찮음..
'BAEKJOON ONLINE JUDGE' 카테고리의 다른 글
| [백준 14890] 경사로 (C++) (0) | 2021.08.20 |
|---|---|
| [백준 19236] 청소년 상어 (C++) (0) | 2021.08.19 |
| [백준 17837] 새로운 게임 2 (C++) (0) | 2021.08.17 |
| [백준 2206] 벽 부수고 이동하기 (C++) (0) | 2021.08.16 |
| [백준 17135] 캐슬 디펜스 (C++) (0) | 2021.08.16 |