[백준] Baekjoon Online Judge
문제
크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.
입력
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.
출력
선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.
제한
- 1 ≤ N, M ≤ 10
- 1 ≤ K ≤ min(4, N×M)
- 격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
- 항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.
풀이
#include <iostream>
using namespace std;
void dfs(int dth, int num, int start);
int N, M, K;
int big = -100000000;
int arr[11][11];
bool check[11][11] = { false };
void dfs(int dth, int num, int start) {
if (dth == K) {
big = max(big, num);
return;
}
for (int i = start; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (check[i][j] || check[i - 1][j] || check[i + 1][j] || check[i][j - 1] || check[i][j + 1]) continue;
check[i][j] = true;
dfs(dth + 1, num + arr[i][j], i);
check[i][j] = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N >> M >> K;
for (int i = 1; i <= N; i++)
for (int j = 1; j <= M; j++) cin >> arr[i][j];
dfs(0, 0, 1);
cout << big << '\n';
return 0;
}
void dfs(int dth, int num, int start) {
if (dth == K) {
big = max(big, num);
return;
}
for (int i = start; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (check[i][j] || check[i - 1][j] || check[i + 1][j] || check[i][j - 1] || check[i][j + 1]) continue;
check[i][j] = true;
dfs(dth + 1, num + arr[i][j], i);
check[i][j] = false;
}
}
}
크기가 N * M인 배열에서 서로 인접하지 않는 K개의 숫자를 선택해 최댓값을 구하는 함수이다. 선택한 숫자의 상하좌우를 확인해야 하므로 배열을 [11][11] 사이즈로 넉넉하게 선언해서 배열을 범위를 넘지 않도록 했다. 상하좌우를 확인할 때 for문을 사용하는 방법도 있으나 최대한 시간을 단축하고 싶었고, 확인하는 경우도 그렇게 많지 않았기에 if문 하나에 모든 조건을 넣는 방식으로 코드를 짰다.
'백준 > C++' 카테고리의 다른 글
[Baekjoon/C++] 15661번 - 링크와 스타트 (0) | 2023.08.25 |
---|---|
[Baekjoon/C++] 14501번 - 퇴사 (0) | 2023.08.24 |
[Baekjoon/C++] 1107번 - 리모컨 (0) | 2023.08.21 |
[Baekjoon/C++] 24092번 - 알고리즘 수업 - 퀵 정렬 3 (1) | 2023.08.19 |
[Baekjoon/C++] 27219번 - Робинзон Крузо (0) | 2023.08.14 |