https://www.acmicpc.net/problem/15898
15898번: 피아의 아틀리에 ~신비한 대회의 연금술사~
"피아의 아틀리에 ~신비한 대회의 연금술사~"는 가난한 연금술사 피아의 성장스토리를 담은 게임이다. 이 게임의 가장 중요한 부분은 "대회"인데, 연금술로 높은 품질의 물건을 만들어 상금을 타
www.acmicpc.net
풀이
속칭 '빡구현'이라는 말이 가장 잘 어울리는 문제입니다. 구현 문제에서 흔히 쓰이는 BFS 정도도 쓰이지 않으며, 모든 경우를 무수한 for문으로 탐색하면 됩니다.
1. 재료 관리
각 칸이든 재료든 '품질'과 '색깔'이라는 두 변수를 갖고 있으니, 같은 class(Status로 정의함)로 관리하면 됩니다. 가마의 상태는 Status[5][5], n개의 재료는 Status[n][4][4]에 저장하도록 합니다.
2. 모든 경우의 수 고려하기
이제, n개의 재료 중 3개의 재료를 뽑아, 배치해야 합니다. 머리 속에서 시뮬레이션을 돌려보면, 넣는 순서가 상관이 있음을 알 수 있습니다. 즉, permutation으로 재료를 뽑을 필요가 있습니다. 또한, 한 재료를 넣을 때 위치는 4군데(0-based 기준으로 (r, c) = (0, 0), (0, 1), (1, 0), (1, 1)) 넣을 수 있고, 회전의 가짓수도 4가지(0도, 90도, 180도, 270도) 이므로, 모든 경우를 고려해야 합니다.
2-1) 재료를 돌리기
- 그림으로 그려서 처리하면 됩니다. 팁으로는, (실제로 들어갈 위치 index) = (재료를 돌려서 나온 위치 index)와 같은 방식으로 처리할 텐데, (실제로 들어갈 위치 index)를 고정하여 생각하면 편합니다. 이 문제 말고도 배열 돌릴 일은 몇번 더 있으니, 본인이 구하는 방법을 정해두면 좋습니다.
2-2) 재료를 넣기
- 가마의 (i+r, j+c)에 회전 처리를 한 재료의 (i, j) 위치 값을 넣습니다. 품질, 색깔 처리도 적절히 합니다.
- 매 시행마다 배열을 call by value로 복사하여, 복사한 배열을 계속 들고다니는 게 편합니다. 백트래킹 식으로 방문했다가 되돌리는 연산을 수행하기엔 너무 번거롭습니다.
2-3) 사소한 팁
- 처음 넣는 재료는 '일반성을 잃지 않고' (0, 0)에만 넣어도 된다는 걸 알 수 있습니다. 따라서 경우를 1/4 줄일 수 있습니다.
3. 계산하기
칸의 색깔별로 점수를 더해주면 됩니다. 쉬워요.
틀렸으면 눈물날 거 같은 문제였는데, 다행히 한 번에 맞았네요 :)
코드
|
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
|
import java.io.*;
import java.util.*;
public class Main {
static int n, ans = -1000000;
static Status[][][] ingridients;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
ingridients = new Status[n][4][4];
visited = new boolean[n];
Status[][] map = new Status[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
map[i][j] = new Status(0, 'W');
}
}
StringTokenizer st;
for (int i = 0; i < n; i++) {
for (int j = 0; j < 4; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 0; k < 4; k++) {
ingridients[i][j][k] = new Status(0, 'W');
ingridients[i][j][k].quality = Integer.parseInt(st.nextToken());
}
}
for (int j = 0; j < 4; j++) {
st = new StringTokenizer(br.readLine());
for (int k = 0; k < 4; k++) {
ingridients[i][j][k].color = st.nextToken().charAt(0);
}
}
}
perm(0, map);
System.out.println(ans);
}
// 10P3의 경우를 모두 세는 method
static void perm(int cnt, Status[][] map) {
if (cnt == 3) {
ans = Math.max(ans, calc(map));
return;
}
for (int idx = 0; idx < n; idx++) {
if (visited[idx]) continue;
visited[idx] = true;
outer: for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
if (cnt == 0 && j > 0) break outer;
for (int dir = 0; dir < 4; dir++) {
Status[][] tempMap = copyMap(map);
put(tempMap, idx, i, j, dir);
perm(cnt+1, tempMap);
}
}
}
visited[idx] = false;
}
}
// 가마의 (r, c)부터 (r+3, c+3) 까지 90*dir도만큼 시계 반대방향으로 회전시킨 재료를 넣는 method
static void put(Status[][] map, int idx, int r, int c, int dir) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (dir == 0) {
map[i+r][j+c].quality += ingridients[idx][i][j].quality;
if (map[i+r][j+c].quality < 0) map[i+r][j+c].quality = 0;
else if (map[i+r][j+c].quality > 9) map[i+r][j+c].quality = 9;
if (ingridients[idx][i][j].color == 'W') continue;
map[i+r][j+c].color = ingridients[idx][i][j].color;
}
else if (dir == 1) {
map[i+r][j+c].quality += ingridients[idx][j][3-i].quality;
if (map[i+r][j+c].quality < 0) map[i+r][j+c].quality = 0;
else if (map[i+r][j+c].quality > 9) map[i+r][j+c].quality = 9;
if (ingridients[idx][j][3-i].color == 'W') continue;
map[i+r][j+c].color = ingridients[idx][j][3-i].color;
}
else if (dir == 2) {
map[i+r][j+c].quality += ingridients[idx][3-i][3-j].quality;
if (map[i+r][j+c].quality < 0) map[i+r][j+c].quality = 0;
else if (map[i+r][j+c].quality > 9) map[i+r][j+c].quality = 9;
if (ingridients[idx][3-i][3-j].color == 'W') continue;
map[i+r][j+c].color = ingridients[idx][3-i][3-j].color;
}
else {
map[i+r][j+c].quality += ingridients[idx][3-j][i].quality;
if (map[i+r][j+c].quality < 0) map[i+r][j+c].quality = 0;
else if (map[i+r][j+c].quality > 9) map[i+r][j+c].quality = 9;
if (ingridients[idx][3-j][i].color == 'W') continue;
map[i+r][j+c].color = ingridients[idx][3-j][i].color;
}
}
}
}
// 품질을 계산하는 method
static int calc(Status[][] map) {
int ret = 0;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++ ) {
int c = 0;
switch (map[i][j].color) {
case 'R':
c = 7;
break;
case 'B':
c = 5;
break;
case 'G':
c = 3;
break;
case 'Y':
c = 2;
break;
}
ret += c*map[i][j].quality;
}
}
return ret;
}
static Status[][] copyMap(Status[][] map) {
Status[][] ret = new Status[5][5];
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++ ) {
ret[i][j] = new Status(map[i][j].quality, map[i][j].color);
}
}
return ret;
}
static class Status {
int quality;
char color;
public Status(int quality, char color) {
this.quality = quality;
this.color = color;
}
}
}
|
cs |
'PS > Implementation' 카테고리의 다른 글
| 백준 21611번: 마법사 상어와 블리자드 (Java) (0) | 2022.07.23 |
|---|---|
| 백준 21609번: 상어 중학교 (Java) (0) | 2022.07.22 |
| 백준 17472번: 다리 만들기 2 (Java) (0) | 2022.07.19 |
| 백준 19236번: 청소년 상어 (Java) (0) | 2022.07.18 |
| 백준 20061번: 모노미노도미노 2 (Java) (0) | 2022.07.15 |