[백준] 20208 - 진우의 민트초코우유 by C++

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

20208번: 진우의 민트초코우유

최근 거의 한 달 동안 매번 풀 때마다 느끼는데

반례도 너무 못찾고 구현력도 웰케 떨어졌는지 모르겠다.

생각하다보면 사고가 그냥 멈춘다. 대체 뭐가 문제일까.

반례도 아니고, 그냥 구현력이 딸려서 2시간 동안 그것만 찾고있었다. 현타가 많이온다....

 

알고리즘 방식

시간복잡도는 O(N!)이고 백트래킹을 통해 풀었다.

N이 최대 10이라

10^10 = (1 * 10) *(2 * 5) * (3 * 3.333) * (4 * 2.5) * (5 * 2) .... (10 * 1)

위의 파란색 부분을 왼쪽으로 이항 시, 10 ^ 8 = 1 * 2 * (3 * 3.333) * (4 * 2.5) * 5 ... (10 * 1) > 10! 이므로

시간초과는 피할 수 있다.

1. 현재 위치 (최초 값은 집)를 통해 다음에 갈 수 있는 우유의 위치를 찾는다.

1-1. 만약 그 우유의 위치가 방문하지 않았다면, 해당 위치의 vis를 1로 바꾼다.

2. 해당 위치에서 집으로 돌아갈 수 있다면, 현재 최대 우유의 개수를 answer에 대입

3. 1.에서 선정한 우유를 현재 위치로하는 함수를 호출한다. (1.로가서 반복)

 

반례

2 2 1
1 0
0 2

36번 째 줄의

disFromHome <= M - disFromExMilk + H

우항 조건을 빼먹고서는 1시간 30분동안 못찾았다....

 

 

소스코드

#include <iostream>
#include <vector>
using namespace std;

//반례
//2 2 1
//1 0
//0 2

vector<pair<int, int>> mintChoco;
int vis[10][10];
pair<int, int> home;
int N, M, H;

int totalMilk;
int answer;

int abs(int x) {
	if (x < 0)
		return x * -1;

	else
		return x;
}

void findMilk(int x, int y, int cntMilk) {
	for (int i = 0; i < totalMilk; i++) {
		pair<int, int> cur = mintChoco[i];
		if (vis[cur.first][cur.second] == 1)
			continue;

		int disFromHome = abs(cur.first - home.first) + abs(cur.second - home.second);
		int disFromExMilk = abs(cur.first - x) + abs(cur.second - y);

		if (disFromExMilk <= M) {
			if (disFromHome <= M - disFromExMilk + H) {
				if (answer < cntMilk + 1)
				answer = cntMilk + 1;
			}
			M -= disFromExMilk - H;
			vis[cur.first][cur.second] = 1;
			//cout << cur.first << ' ' << cur.second << ' ' << cntMilk + 1 << ' ' <<  M << '\n';
			findMilk(cur.first, cur.second, cntMilk + 1);
			vis[cur.first][cur.second] = 0;
			M += disFromExMilk - H;
		}
	}
}


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> H;

	int inp;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> inp;
			if (inp == 2)
				mintChoco.push_back({ i, j });
			if (inp == 1)
				home = { i, j };
		}
	}
	totalMilk = mintChoco.size();
	findMilk(home.first, home.second, 0);

	cout << answer;
}