https://www.acmicpc.net/problem/3085
3085번: 사탕 게임
문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고
www.acmicpc.net
방법 1: 라이브러리 활용X
|
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
|
#include <iostream>
using namespace std;
const int MAX = 50;
int get_max_after_swap(const char board[][MAX], int N, int x, int y)
{
int max = 0;
// 가로
for (int i = x; i < N && i < x + 2; i++)
{
int h_max = 1;
for (int j = 0; j < N - 1; j++)
{
if (board[i][j] == board[i][j + 1])
{
h_max++;
max = (max < h_max) ? h_max : max;
}
else
{
h_max = 1;
}
}
}
// 세로
for (int j = y; j < N && j < y + 2; j++)
{
int v_max = 1;
for (int i = 0; i < N - 1; i++)
{
if (board[i][j] == board[i + 1][j])
{
v_max++;
max = (max < v_max) ? v_max : max;
}
else
{
v_max = 1;
}
}
}
return max;
}
int get_max_count(const char board[][MAX], int N)
{
int max = 0;
for (int i = 0; i < N; i++)
{
// 가로
int t_max = 1;
for (int j = 0; j < N - 1; j++)
{
if (board[i][j] == board[i][j + 1])
{
t_max++;
max = (max < t_max) ? t_max : max;
}
else
{
t_max = 1;
}
}
// 세로
t_max = 1;
for (int j = 0; j < N - 1; j++)
{
if (board[j][i] == board[j + 1][i])
{
t_max++;
max = (max < t_max) ? t_max : max;
}
else
{
t_max = 1;
}
}
}
return max;
}
void swap(char* A, char* B)
{
char tmp = *A;
*A = *B;
*B = tmp;
}
int main()
{
int N;
cin >> N;
char board[MAX][MAX] = { 0, };
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> board[i][j];
}
}
// 인접한 사탕을 교환하기 전, 전체 보드에서 사탕 최대개수 구하기
int max = get_max_count(board, N);
// 인접한 두 사탕을 가로/세로로 교환하면서 사탕 최대개수 구하기
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
// 가로
if (j < N - 1)
{
swap(&board[i][j], &board[i][j + 1]);
// 교환한 사탕이 포함된 2*2 행/렬만 검사
int t_max = get_max_after_swap(board, N, i, j);
swap(&board[i][j], &board[i][j + 1]);
max = (max < t_max) ? t_max : max;
}
// 세로
if (i < N - 1)
{
swap(&board[i][j], &board[i + 1][j]);
// 교환한 사탕이 포함된 2*2 행/렬만 검사
int t_max = get_max_after_swap(board, N, i, j);
swap(&board[i][j], &board[i + 1][j]);
max = (max < t_max) ? t_max : max;
}
}
}
cout << max;
return 0;
}
Colored by Color Scripter
|
방법 2: 라이브러리 활용O
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int get_max_after_swap(const vector<string> &board, int x, int y)
{
int N = board.size();
int max = 0;
// 가로
for (int i = x; i < N && i < x + 2; i++)
{
int h_max = 1;
for (int j = 0; j < N - 1; j++)
{
if (board[i][j] == board[i][j + 1])
{
h_max++;
max = (max < h_max) ? h_max : max;
}
else
{
h_max = 1;
}
}
}
// 세로
for (int j = y; j < N && j < y + 2; j++)
{
int v_max = 1;
for (int i = 0; i < N - 1; i++)
{
if (board[i][j] == board[i + 1][j])
{
v_max++;
max = (max < v_max) ? v_max : max;
}
else
{
v_max = 1;
}
}
}
return max;
}
int get_max_count(const vector<string> &board)
{
int N = board.size();
int max = 0;
for (int i = 0; i < N; i++)
{
// 가로
int t_max = 1;
for (int j = 0; j < N - 1; j++)
{
if (board[i][j] == board[i][j + 1])
{
t_max++;
max = (max < t_max) ? t_max : max;
}
else
{
t_max = 1;
}
}
// 세로
t_max = 1;
for (int j = 0; j < N - 1; j++)
{
if (board[j][i] == board[j + 1][i])
{
t_max++;
max = (max < t_max) ? t_max : max;
}
else
{
t_max = 1;
}
}
}
return max;
}
int main()
{
int N;
cin >> N;
vector<string> board(N);
for (int i = 0; i < N; i++)
{
cin >> board[i];
}
// 인접한 사탕을 교환하기 전, 전체 보드에서 사탕 최대개수 구하기
int max = get_max_count(board);
// 인접한 두 사탕을 가로/세로로 교환하면서 사탕 최대개수 구하기
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
// 가로
if (j < N - 1)
{
swap(board[i][j], board[i][j + 1]);
// 교환한 사탕이 포함된 2*2 행/렬만 검사
int t_max = get_max_after_swap(board, i, j);
swap(board[i][j], board[i][j + 1]);
max = (max < t_max) ? t_max : max;
}
// 세로
if (i < N - 1)
{
swap(board[i][j], board[i + 1][j]);
// 교환한 사탕이 포함된 2*2 행/렬만 검사
int t_max = get_max_after_swap(board, i, j);
swap(board[i][j], board[i + 1][j]);
max = (max < t_max) ? t_max : max;
}
}
}
cout << max;
return 0;
}
Colored by Color Scripter
|
방법 1,2는 로직의 차이가 있는게 아니라,
그냥 자료구조를 바꾼것 뿐이다.
복잡도는 둘다 O(N^3)
TIP
N×N크기의 사탕상자.
사탕의 색이 다른 인접한 두 칸의 사탕을 서로 교환한다.
이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다.
먹을 수 있는 사탕의 최대 개수를 구하는 프로그램을 작성하시오.
문제에 힌트 또는 함정(?)이 있다.
인접한 두칸의 사탕을 교환했다면, 교환하지 않은 나머지 칸들의 상태는 어떠할까?
당연하게도,,, 교환하기 전 후가 같다.
즉, 교환할 때마다 사탕 상자 전체를 확인할 필요가 없고 (방법 2),
처음 한번만 전체를 확인하면 된다.
그다음부터는 교환의 영향이 미치는 행, 열만 확인해주면 된다. (방법 1)
사실 왼/오 또는 위/아래를 교환하면
변화되는 행 또는 열은 총 3개 라인이다.
(왼/오 : 행1개 열2개, 위/아래 : 행2개 열1개)
하지만, 이 문제가 코딩테스트에서 나왔다고 생각하면
예외처리를 그렇게 많이 할 겨를이 없을 것 같다.
그래서 약간의 중복을 감수하고
왼/오 위/아래 모두 행2개 열2개씩 확인하도록 했다.
'Algorithm > BOJ' 카테고리의 다른 글
| [BOJ]14500번: 테트로미노(c++) (0) | 2020.05.03 |
|---|---|
| [BOJ]1107번: 리모컨(c++) (0) | 2020.05.03 |
| [BOJ]2225번: 합분해(c++) 심화(이지만 더 쉬운!) (0) | 2020.04.27 |
| [BOJ]17404번: RGB거리 2(c++) (0) | 2020.04.27 |
| [BOJ]11656번: 접미사 배열(c++) (0) | 2020.04.25 |
댓글