백준 12033, 김인천씨의 식료품가게 (Small)

문제

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

풀이 방법

사실 풀이 방법이라 할 것도 없이 testcase 100, 한 case에서 최대 물건 개수는 8개(4 * 2)이므로 어떤 방법으로든지 구현만 하면 풀리는 문제이다.

다만 나같은 경우에는 결과를 저장하는 벡터 result를 만들어서 짝이 없는 경우에는 맨 뒤에 삽입, 짝이 없는데 수의 관계가 3 : 4를 만족하면 second에 삽입하는 방식으로 진행했다.

result에서 짝을 찾는 경우 n, 총 물건 개수 2n해서 O(n^2 * t)이므로 아주 널널하게 풀리는 것을 확인할 수 있다.

실수

• 딱히 없었다. 벡터 사용이 거의 처음이라 미숙했고 cin 대신 scanf를 사용한 것을 빼면 지금까지와 같았다.

코드

#define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>

using namespace std;

void solution(int n, int t) {

	vector<int> input; // 입력값 벡터
	vector<pair<int, int>> result; // 결과 값을 저장할 벡터

	for (int i = 0; i < 2 * n; i++) {

		int temp;

		scanf("%d", &temp);

		input.push_back(temp);

	}

	for (int i = 0; i < 2 * n; i++) {

		bool check_insert = false; // 삽입에 성공했는지 확인하는 변수

		for (int j = 0; j < result.size(); j++) { // 이미 넣은 결과 값과 비교해서 3 : 4 관계가 성립하면 second에 삽입

			if (result[j].second == 0 && result[j].first == input[i] * 0.75) { // second가 0이 아닌 경우 둘다 채워져 있음으로 삽입하지 않음

				result[j].second = input[i];
				check_insert = true;
				
				break;

			}

		}

		if (check_insert == false) { // 짝이 없는 경우 맨 뒤에 삽입

			result.push_back(make_pair(input[i], 0));

		}

	}

	printf("Case #%d: ", t);

	for (int i = 0; i < n; i++) {

		printf("%d ", result[i].first);

	}

	return;

}

int main() {

	int t;

	scanf("%d", &t);

	for (int i = 0; i < t; i++) {

		int n;

		scanf("%d", &n);

		solution(n, i + 1);

	}

	return 0;

}