NM과 K (1) 18290

NM과 K (1) (18290)

 

풀이코드 (1)

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 18290 NM과 K (1)

int N, M, K;
int board[10][10];
bool used[10][10];

int coord[4][4] = {
	{0, 1},
	{1, 0},
	{-1, 0},
	{0, -1}
};

int maxSum = -123456789;

void go(int count, int sum){
	if(count == K){
		if( maxSum < sum ) maxSum = sum;
		return;
	}
	for(int y = 0; y < N; y++){
		for(int x = 0; x < M; x++){
			// 사용할 수 없다면 넘어감
			if(used[y][x]) continue;
			
			bool ok = true;
			for(int i = 0; i < 4; i++){
				int ny = y + coord[i][0];
				int nx = x + coord[i][1];
				//범위가 정상이고
				if( 0 <= nx && nx < M && 0 <= ny && ny < N){
					// 해당 칸이 사용되었다면 ok = false
					if(used[ny][nx]) ok = false;
				}
			}
			// [y][x] 칸 주변이 모두 사용 가능하다면 재귀함수를 들어감.
			if(ok){
				used[y][x] = true;
				go(count + 1, sum + board[y][x]);
				used[y][x] = false;
			}
			
			
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N >> M >> K;
	cin.ignore();
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> board[i][j];
		}
	}
	
	fill_n(used[0], 100, false);
	go(0, 0);
	cout << maxSum << '\n';
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

풀이

1. 브루트 포스로 할 수 있을까?

- 경우의 수의 최대치는 (10 * 10)C(4) 이므로, 약 300만이다. 1억에 미치지 못하므로 브루트 포스로의 접근이 가능하다.

- 하지만, 선택. 하나의 칸을 선택하느냐 마냐의 경우의 수는 2^100 이므로 1억을 훌쩍 넘는다. 브루트 포스로는 불가능하겠지만 메모이제이션을 활용한 "선택" 브루트 포스 는 가능할 것이다. 

2. 수의 최대치

- 10,000 이 최대치이므로 모든 합이 정수형을 벗어날 수 잇으므로 최댓값을 갖는 변수는 long long 이 적당하겠다.

3. 44번째 줄의 아이디어

- 처음 문제를 접하였을 때, 선택을 하는 브루트 포스를 구상하였었다. 그런데, 조건을 문제 그대로 "한 칸을 선택하고 주변 칸들을 사용불가하게 만들어 재귀" 로 했었다. 그 대신, "한 칸을 선택하고 주변 칸들이 전부 사용가능하다면 해당 칸을 선택" 하는 것으로 하였더니 깔끔했다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

시간복잡도가 크다. 

$$O((NM)^K)$$

중복 선택이 너무 많다는 것이다. NM 을 검사한 뒤, 또 다시 NM 을 검사하게 되어 순서만 다른, 경우의 수를 중복 계산할 수 있다는 것이다. 중복 계산을 피하기 위해 "시작점" 을 재귀 파라미터에 넣었다.

지금까지 배운 재귀는 일관성을 가진다. "어떤 위치에서든 같은 방법으로 수를 골라야 한다."

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 18290 NM과 K (1)

int N, M, K;
int board[10][10];
bool used[10][10];

int coord[4][4] = {
	{0, 1},
	{1, 0},
	{-1, 0},
	{0, -1}
};

int maxSum = -123456789;

void go(int count, int sum, int startY, int startX){
	if(count == K){
		if( maxSum < sum ) maxSum = sum;
		return;
	}
	for(int y = startY; y < N; y++){
		for(int x = (y == startY ? startX : 0); x < M; x++){
			// 사용할 수 없다면 넘어감
			if(used[y][x]) continue;
			
			bool ok = true;
			for(int i = 0; i < 4; i++){
				int ny = y + coord[i][0];
				int nx = x + coord[i][1];
				//범위가 정상이고
				if( 0 <= nx && nx < M && 0 <= ny && ny < N){
					// 해당 칸이 사용되었다면 ok = false
					if(used[ny][nx]) ok = false;
				}
			}
			// [y][x] 칸 주변이 모두 사용 가능하다면 재귀함수를 들어감.
			if(ok){
				used[y][x] = true;
				
				int nextY = (x == M - 1) ? y + 1 : y;
				int nextX = (x == M - 1) ? 0 : x + 1;
				
				go(count + 1, sum + board[y][x], nextY, nextX);
				used[y][x] = false;
			}
			
			
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	cin >> N >> M >> K;
	cin.ignore();
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < M; j++){
			cin >> board[i][j];
		}
	}
	
	fill_n(used[0], 100, false);
	go(0, 0, 0, 0);
	cout << maxSum << '\n';
}

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점

go 함수의 for 문에서 int x 를 왜 저렇게 초기화 하였는지가 중요했다. 처음 시작점을 잡을 때는 startX 로 x 를 선언하는 것이 맞지만 그 이후의 y 에서는 0부터 시작하는 것이 맞기 때문이다.

 

여러 시도를 해보느라 많이 틀렷다.. 너무 막무가내였다