중급반 1주차 풀이 - Brute Force

1. [2309] 일곱 난쟁이 (Bronze I)

정답인 7명을 다 고르는 건 힘든 작업입니다. 그러니까 정답이 아닌 2명을 골라봅시다.

9명의 키의 합 - (빼는 2명의 키의 합) = 100인 2명을 고르면 되고, \( O(N^2) \)에 해결할 수 있습니다.

int arr[10];

void Main(){
	int n; cin >> n; int sum = 0;
	for (int i = 1; i <= 9; i++){ cin >> arr[i]; sum += arr[i]; }
	sort(arr+1, arr+10);
	for (int i = 1; i <= 9; i++){
		for (int j = i+1; j <= 9; j++){
			if (sum-arr[i]-arr[j] == 100){
				for (int k = 1; k <= 9; k++){
					if (k == i || k == j){ continue; }
					cout << arr[k] << endl;
				}
				return;
			}
		}
	}
}

2. [18111] 마인크래프트 (Silver III)

만들고 싶은 평지의 높이를 \( h \)로 고정해봅시다.

인벤토리에 넣을 수 없는 블럭의 개수 제한은 없으므로, 평지를 만들 때 \( h \)보다 위에 있는 모든 블럭을 제거한 뒤, \( h \)보다 낮은 위치에 블럭을 메꿔주면 됩니다.

이제, 위 방식을 가능한 모든 평지의 높이 (0 ~ 256)로 돌려주면 됩니다. 이 때의 시간복잡도는 \( O(NMH) \)입니다.

int arr[520][520];

void Main(){
	int n, m; ll k; cin >> n >> m >> k;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> arr[i][j];
		}
	}
	ll ans = 1e18, mxp = 0;
	for (int h = 0; h <= 256; h++){
		ll brk = 0, plc = 0;
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= m; j++){
				if (arr[i][j] > h){ brk += arr[i][j]-h; }
				if (arr[i][j] < h){ plc += h-arr[i][j]; }
			}
		}
		if (k+brk < plc){ continue; }
		ll res = 2*brk + plc;
		if (res <= ans){ ans = res; mxp = h; }
	}
	cout << ans << ' ' << mxp;
}

3. [1065] 한수 (Silver IV)

한수를 판별하는 함수를 만들어봅시다. 이 함수가 있다면, 1부터 N까지 직접 함수를 돌려가면서 개수를 세주면 됩니다.

 

한수 구현이 생각보다 귀찮을 수도 있기 때문에, 입력 범위와 한수를 분석해봅시다.

2자리 수 이하는 항상 한수입니다. (길이 2 이하의 수열 = 등차수열)

4자리 수 이상은 1000 말고 들어오지 않으며, 1000은 한수가 아닙니다.

그러므로, 3자리 수에 대해서만 판별해주면 되고, \( n = 100a + 10b + c \)일 때 \( a-b = b-c \)를 보면 됩니다.

시간복잡도는 \( O(N) \)입니다.

bool f(int x){
	if (x < 100){ return 1; } if (x >= 1000){ return 0; }
	int a = x/100, b = x/10%10, c = x%10;
	return a-b == b-c;
}

void Main(){
	int n; cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; i++){ ans += f(i); }
	cout << ans;
}

4. [16464] 가주아 (Silver III)

선택한 카드의 개수를 \( m \)개라고 합시다.

이 때 만들 수 있는 모든 수는 \( (1+k) + (2+k) + \cdots + (m+k) = \frac{m(m+1)}{2} + mk \)가 됩니다.

이 때 \( k \)는 음이 아닌 정수여야 합니다.

그러므로, 카드를 정확히 \( m \)개 사용하여 합을 \( K \)로 만들 수 있다는 건 다음을 의미합니다.

• \( K \ge \frac{m(m+1)}{2} \)이며, \( K - \frac{m(m+1)}{2} \)는 \( m \)의 배수이다.

이제 위 과정을 \( K \ge \frac{m(m+1)}{2} \)인 모든 \( m \)에 대해 돌려주면 됩니다.

시간복잡도는 \( O(T \cdot \sqrt{K}) \)가 됩니다.

// N -> t / K -> n / m -> k
void Main(){
	int t; cin >> t;
	while (t--){
		ll n; cin >> n; bool ans = 0;
		for (ll k = 2; ; k++){
			ll st = k*(k+1) / 2;
			if (n < st){ break; }
			if ( (n-st) % k == 0 ){ ans = 1; break; }
		}
		cout << (ans ? "Gazua" : "GoHanGang") << endl;
	}
}

5. [14500] 테트로미노 (Gold V)

회전이나 대칭 이동을 '다른 종류'로 고려하면, 테트로미노의 종류는 총 19가지가 됩니다.

이 19가지의 모양 중 하나를 골라봅시다.

그 모양에서의 최댓값은, 그 모양을 가능한 모든 곳에 놓아보는 방식으로 찾을 수 있습니다.

최종 답은 위 19가지 모양의 결과 중 최댓값이 됩니다.

시간복잡도는 \( O(19 \cdot 16 \cdot NM) \)이 됩니다.

int blk[22][4][4];
int arr[520][520];

/* blk, #=1, .=0

#### #...
.... #...
.... #...
.... #...

##..
##..
....
....

###. .#.. .#.. #...
.#.. ##.. ###. ##..
.... .#.. .... #...
.... .... .... ....

#... .##.
##.. ##..
.#.. ....
.... ....

.#.. ##..
##.. .##.
#... ....
.... ....

#... ..#. ##.. ###.
#... ###. .#.. #...
##.. .... .#.. ....
.... .... .... ....

.#.. #... ##.. ###.
.#.. ###. #... ..#.
##.. .... #... ....
.... .... .... ....

*/

void Main(){
	int n, m; cin >> n >> m;
	for (int y = 1; y <= n; y++){
		for (int x = 1; x <= m; x++){
			cin >> arr[y][x];
		}
	}
	int ans = 0;
	for (int y = 1; y <= n; y++){
		for (int x = 1; x <= m; x++){
			for (int k = 1; k <= 19; k++){
				int res = 0;
				for (int i = 0; i < 4; i++){
					for (int j = 0; j < 4; j++){
						res += arr[y+i][x+j] * blk[k][i][j];
					}
				}
				ans = max(ans, res);
			}
		}
	}
	cout << ans;
}

6. [1476] 날짜 계산 (Silver V)

(E, S, M) = (1, 1, 1)부터 시작해서, 입력받은 값과 동일할 때까지 E, S, M을 올려주면 됩니다.

 

+ E, S, M의 최댓값 (15, 28, 19)의 특성상 답이 존재하지 않는 경우는 없습니다.

시간복잡도는 \( O(ESM) \)입니다.

void Main(){
	int a, b, c; cin >> a >> b >> c;
	int i = 1, j = 1, k = 1;
	for (int ans = 1; ; ans++){
		if (i==a && j==b && k==c){ cout << ans; return; }
		i += 1; if (i > 15){ i = 1; }
		j += 1; if (j > 28){ j = 1; }
		k += 1; if (k > 19){ k = 1; }
	}
}

7. [15686] 치킨 배달 (Gold V)

치킨집의 개수를 편의상 \( K \)개라고 해봅시다. 입력 조건에 의해, \( K \le 13 \)입니다.

그러니, 가능한 모든 치킨집의 경우를 다 돌려볼 수 있습니다.

 

이제 각각의 경우에 대해, 각 집에서 치킨집까지의 거리의 최솟값의 합을 직접 구할 수 있습니다.

전체 문제의 답은 각 경우의 답 중 가장 작은 값이 됩니다.

시간복잡도는 \( O(2^{K} \cdot 2N \cdot M) \)입니다.

 

+ 사실 치킨집을 더 만들어서 생기는 손해는 없습니다. 즉, 치킨집이 \( M \)개인 경우만 탐색해줘도 됩니다.

int n, m;
vector<pi2> arr, chk;

vector<pi2> vec; int ans = 1e9;
void btk(int cnt, int idx){
	if (cnt == m){
		int res = 0;
		for (pi2 p1 : arr){
			int mn = 1e9;
			for (pi2 p2 : vec){ mn = min(mn, abs(p1.fr-p2.fr) + abs(p1.sc-p2.sc)); }
			res += mn;
		}
		ans = min(ans, res);
		return;
	}
	for (int i = idx+1; i < chk.size(); i++){
		vec.push_back(chk[i]); btk(cnt+1, i);
		vec.pop_back();
	}
}

void Main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			int x; cin >> x;
			if (x == 1){ arr.push_back({i, j}); }
			if (x == 2){ chk.push_back({i, j}); }
		}
	}
	btk(0, -1); cout << ans;
}

8. [1107] 리모컨 (Gold V)

숫자를 눌러서 채널을 바꾸는 건 시작할 때 1번 하는 것으로 충분합니다.

그러니, 처음 시작할 때 숫자를 사용해서 갈 채널을 선택한 뒤, 그 채널에서 목표 채널까지 +나 -를 열심히 눌러주는 방식으로 문제를 풀 수 있습니다.

 

처음 시작할 때 갈 수 있는 채널은 1000000까지로 제한할 수 있으니, 가능한 시작 채널을 모두 돌려보면 됩니다.

시간복잡도는 \( O(X=1000000) \)입니다.

bool chk[12];

void Main(){
	int ed; cin >> ed;
	int m; cin >> m;
	while (m--){ int x; cin >> x; chk[x] = 1; }
	int ans = abs(ed-100);
	for (int i = 0; i <= 1000000; i++){ int st = i;
		int res = 0;
		if (st == 0){ if (chk[0]){ goto next; } else{ res = 1; } }
		while (st){
			if (chk[st%10]){ goto next; }
			res += 1; st /= 10;
		}
		res += abs(i-ed);
		ans = min(ans, res);
		next: ;
	}
	cout << ans;
}