[백준 / C++] 18290번: NM과 K (1)

https://www.acmicpc.net/problem/18290

18290번: NM과 K (1)

 

난이도: solved.ac 실버 1

 

알고리즘 분류

브루트포스 알고리즘, 백트래킹

 

구현 방법

이전에 풀었던 백준 14502번 연구소 문제 (https://jangkunstory.tistory.com/135)에서 구현했던 걸 구현하는 문제다.

 

N*M개에서 K개 고르기.

 

연구소 문제에서는 next_permutation 함수를 이용해 nC3을 구현했지만 이번에는 다른 방식으로 풀었다.

(그래도 시간은 20ms으로 다른 분들보다 상대적으로 적게 걸렸다.)

 

(1,1)부터 시작해 (1,1), (1,2), (1,3), ... , (N,M-1), (N,M) 처럼 오른쪽으로 한 칸씩 이동하며 수를 골랐고,

 

수를 골랐다면 오른쪽 두 칸으로 이동해 재귀함수를 호출하며 다음 수를 고르게 했다.

 

그리고 인접한 영역에 이미 고른 수가 있으면 안되므로 한 칸 위에 고른 수가 없는 영역만 선택하도록 했다.

 

(1,1)부터 오른쪽으로 이동하므로 인접한 오른쪽, 아래쪽은 당연히 아직 선택하지 않았고, 수를 고르고 나서는 두 칸 옆으로 이동했기 때문에 인접한 왼쪽 칸은 보지 않아도 된다.

 

그리고 선택한 수가 K개가 되면 그 합이 ans보다 크면 ans을 갱신하도록 했다.

 

코드

#include <bits/stdc++.h>
using namespace std;
int N, M, K, ans = -40000;
int arr[11][11], visited[11][11];
void backtr(int r, int c, int num, int sum);

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int i, j;
	cin >> N >> M >> K;
	for (i = 1; i <= N; i++)
		for (j = 1; j <= M; j++)
			cin >> arr[i][j];
	backtr(1, 1, 0, 0);
	cout << ans;
}

void backtr(int r, int c, int num, int sum) {
	if (num == K) {
		if (sum > ans)
			ans = sum;
		return;
	}
	if (c > M) {
		r++;
		c = 1;
	}
	if (r > N)
		return;
	int i = r, j = c;
	while (i <= N) {
    		// 바로 윗 칸의 수를 선택하지 않았을 때만
		if (!visited[i - 1][j]) {
			visited[i][j] = 1;
            		// 두 칸 옆으로 이동
			backtr(i, j + 2, num + 1, sum + arr[i][j]);
			visited[i][j] = 0;
		}
		j++;
		if (j > M) {
        	// 다음 행으로 이동
			i++;
			j = 1;
		}
	}
}

 

성능

코드 제출 결과