S사 기출 문제이다. 2차원 맵에 value 값이 있으면 그 값을 나머지 맵에 비율에 따라 분배하는 문제이다.
문제를 풀기 위해서는
1) 나선형으로 순회
2) 값 분배
과정이 필요하다.
1) 나선형으로 순회
나같은 경우에는 새로운 시작이 될 때는 무조건 하나씩 왼쪽으로 가서 시작하도록 했다. 그 다음은 (1->1->2->2->2)->(1->3->4->4->4)->(1->5->6->6->6) ... 이 되도록 하였다.
|
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
|
x = (n - 1) / 2; y = (n - 1) / 2; k = 1; cnt = (n - 1) / 2;
while (cnt--) {
////left
x -= 1;
ans += LeftRight(y, x, 1);
for (int t = 0; t < k; t++) {
//down
y += 1;
ans += UpDown(y, x, -1);
}
k++;
for (int t = 0; t < k; t++) {
//right
x += 1;
ans += LeftRight(y, x, -1);
}
for (int t = 0; t < k; t++) {
//up
y -= 1;
ans += UpDown(y, x, 1);
}
for (int t = 0; t < k; t++) {
//left
x -= 1;
ans += LeftRight(y, x, 1);
}
k++;
}
|
cs |
2) 다음으로는 값들을 분배해주었다.
왼쪽 오른쪽 위 아래 4방향으로 갈 수 있었는데, 나같은 경우에는 left, right를 한 함수에 up, down을 한 함수에 처리해주었다. 그리고 대칭되는 위치가 있기 때문에 나머지 연산을 이용해서 풀이를 하였다.
- 왼쪽 , 오른쪽
|
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
|
int LeftRight(int i, int j, int flag) {
int val, sum, tot;
int nx, ny;
val = sail[i][j];
sail[i][j] = 0;
sum = 0;
// 0부터
nx = (dx[0] * flag) + j; ny = dy[0] + i;
tot = (val * 5) / 100;
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 5) / 100;
else
sum += (val * 5) / 100;
for (int m = 1; m < 10; m++) {
nx = (dx[m] * flag) + j; ny = dy[m] + i;
// 10%
if (m % 5 == 1) {
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 10) / 100;
else
sum += (val * 10) / 100;
tot += (val * 10) / 100;
}else if (m % 5 == 2) { // 7%
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 7) / 100;
else
sum += (val * 7) / 100;
tot += (val * 7) / 100;
}
else if (m % 5 == 3) { // 2%
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 2) / 100;
else
sum += (val * 2) / 100;
tot += (val * 2) / 100;
}else if (m % 5 == 4) { // 1%
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 1) / 100;
else
sum += (val * 1) / 100;
tot += (val * 1) / 100;
}
}
// 마지막 나머지
nx = (dx[5] * flag) + j; ny = dy[5] + i;
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val - tot);
else
sum += (val - tot);
return sum;
}
|
cs |
- 위 아래
위 아래는 x, 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
|
int UpDown(int i, int j, int flag) {
int val, sum, tot;
int nx, ny;
val = sail[i][j];
sail[i][j] = 0;
sum = 0;
// 5%
nx = j + dy[0]; ny = i + (dx[0] * flag);
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 5) / 100;
else
sum += (val * 5) / 100;
tot = ((val * 5) / 100);
for (int m = 1; m < 10; m++) {
nx = dy[m] + j; ny = (dx[m] * flag) + i;
// 10%
if (m % 5 == 1) {
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 10) / 100;
else
sum += (val * 10) / 100;
tot += ((val * 10) / 100);
}
else if (m % 5 == 2) { // 7%
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 7) / 100;
else
sum += (val * 7) / 100;
tot += ((val * 7) / 100);
}
else if (m % 5 == 3) { // 2%
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += (val * 2) / 100;
else
sum += (val * 2) / 100;
tot += ((val * 2) / 100);
}
else if (m % 5 == 4) { // 1%
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] += ((val * 1) / 100);
else
sum += ((val * 1) / 100);
tot += ((val * 1) / 100);
}
}
// 마지막 나머지
nx = dy[5] + j; ny = (dx[5] * flag) + i;
if (nx >= 0 && ny >= 0 && nx < n && ny < n)
sail[ny][nx] = sail[ny][nx] + (val - tot);
else
sum += (val - tot);
return sum;
}
|
cs |
728x90
'개발 > 알고리즘' 카테고리의 다른 글
| 11004_K번째 수 (0) | 2020.11.15 |
|---|---|
| 10825_국영수 (0) | 2020.11.14 |
| 2133_Tri Tiling(DP) (0) | 2020.10.31 |
| 11726번: 2×n 타일링 (0) | 2020.10.25 |
| 알고리즘 입출력_ (0) | 2020.10.11 |