728x90
반응형
https://www.acmicpc.net/problem/3085
3085번: 사탕 게임
문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하
www.acmicpc.net
|
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
|
#define NSIZE 51
#include<stdio.h>
#include<iostream>
using namespace std;
int N;
char input[NSIZE][NSIZE];
int Max = 0x80000000;
void init() {
cin >> N;
for (int i = 0; i < N; i++)
cin >> input[i];
}
void chkMax() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int cnt = 0;
int x = j;
while (x < N && input[i][j] == input[i][x]) x++,cnt++;
if (Max < cnt)Max = cnt;
cnt = 0;
int y = i;
while (y < N && input[i][j] == input[y][j])y++,cnt++;
if (Max < cnt)Max = cnt;
}
}
}
void changeCandy() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j + 1 < N && input[i][j] != input[i][j + 1]) {
swap(input[i][j], input[i][j + 1]);
chkMax();
swap(input[i][j], input[i][j + 1]);
}
if (i + 1 < N && input[i][j] != input[i + 1][j]) {
swap(input[i][j], input[i + 1][j]);
chkMax();
swap(input[i][j], input[i + 1][j]);
}
}
}
}
int main(void) {
init();
//kMax();
changeCandy();
cout << Max << endl;
return 0;
}
|
이문제는 정말 쉬운게 그냥 행을 움직이면서 두개가 다른 캔디면 바꾸고
열을 움직이면 다른캔디면 바꾸고
하는 과정에서 최대길이가 몇인지 최댓값을 찾아 출력만 해주면 됩니다. 처음에 실수한것이 최댓값을 제대로 검색을 안해서틀렸는데 그냥 정말 한개씩 쭉 길이 찾아주면되는 완전 탐색문제 입니다.
이런 식으로 전부 검사를 해야 맞습니다. 제가 이부분에서 간단한 실수를 해서 좀 난감 했습니다.
오늘은 여기까지이고 내일도 좋은 알고로 찾아 뵙겠습니다.
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 2151 거울 설치 (0) | 2019.10.11 |
|---|---|
| 백준 5213 과외맨 (0) | 2019.10.11 |
| 백준 14395 4연산 (0) | 2019.10.08 |
| 백준 9944 NxM 보드 완주하기 (0) | 2019.10.08 |
| 백준 2234 성곽 (0) | 2019.10.07 |
댓글