[ 문제 ]

[ 구현 ]
분할정복 + 해 구성하기 느낌으로 풀었다
핵심 아이디어는
주어진 n을 2등분해 나가면서 절반은 A로 나머지 절반은 B로 바꿔주는 것이다.
이러한 분할정복 방식을 통한다면 2^7은 128이므로 n<=99의 조건을 충분히 커버할 수 있게 된다.
(이를 위해 배열도 2차원으로 두어 몇번째 대진표에 해당하는 것인지 따로 저장해줄 필요가 있음)
조금 예외적인 상황으로
항상 7개의 대진표를 출력해야하며, 각 팀에 원숭이가 최소 1마리는 있어야 하는 조건을 만족해야 하므로
추가적인 처리가 필요하다.
[ 코드 ]
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int print_cnt = 0;
char arr[8][100];
void dq(int st, int ed, int depth) {
print_cnt = max(print_cnt, depth);
if (st >= ed || depth == 7) return;
int mid = (st + ed) / 2;
for (int i = st; i <= ed; i++) {
if (i <= mid) arr[depth][i] = 'A';
else arr[depth][i] = 'B';
}
dq(st, mid, depth+1);
dq(mid+1, ed, depth+1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
dq(0, n - 1, 0);
for (int i = 0; i < print_cnt; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] == '\0') {
arr[i][j] = 'A';
}
cout << arr[i][j];
}
cout << '\n';
}
while (print_cnt < 7) {
cout << 'A';
for (int i = 1; i < n; i++) {
cout << 'B';
}
cout << '\n';
print_cnt++;
}
return 0;
}
[ 마무리 및 느낀 점 ]
아이디어는 비교적 단순하지만 구현의 세부적인 처리에서 어려움을 느꼈다.
주기적으로 조금씩 문제를 풀어주면서 감을 잃지 말아야겠다.
'Algorithm > 백준' 카테고리의 다른 글
| [백준/c++] 1956번 - 운동 (0) | 2024.02.19 |
|---|---|
| [백준/c++] 2629번 - 양팔저울 (0) | 2024.02.19 |
| [백준/c++] 1937번 - 욕심쟁이 판다 (0) | 2024.01.30 |
| [백준/c++] 15311번 - 약 팔기 (0) | 2024.01.22 |
| [백준/c++] 11657번 - 타임머신 (1) | 2024.01.21 |