굳건하게

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 문제인 'Order'를 다뤄보겠습니다.

문제를 읽었을 땐 되게 어렵다고 느꼈지만, 간단한 아이디어로 구현할 수 있어서 금방 해결한 문제입니다.

[문제해석]

N명의 사람이 일렬로 서있고, 모든 사람들은 1 ~ N까지 숫자 중에 겹치지 않게 숫자를 하나 부여받는다고 하자.

이때, N개의 값이 주어지고 이 값들은 왼편에 있는 사람 중 나보다 값이 적은 사람의 수라고 하자.

N개의 값이 유효한지 아닌지 판단해라.

위의 예제를 통해 문제를 조금 더 이해해보자.

10명의 사람이 있고 [0 0 0 2 0 1 6 7 6 9] 라는 배열이 주어졌을 때, [6 4 3 5 1 2 8 9 7 10] 배열에 대해 생각해보자.

'4'번 번호를 부여받은 사람은 왼쪽에 자기보다 큰 '6' 만 존재하고,

'3'번 번호를 부여받은 사람은 마찬가지로 왼쪽에 자기보다 큰 '6', '4' 만 존재하므로 [0 0 0 ~ ]이 되고,

'5'번 번호를 부여받은 사람은 왼쪽에 자기보다 작은 '4', '3' 존재하므로 [0 0 0 2 ~ ]이 성립한다.

[알고리즘설계]

1. N개의 배열이 주어졌을 때, 이 배열은 왼쪽에 나보다 작은 사람의 수를 의미하므로 앞에서부터 순회하며 내 오른쪽에는 사람이 없다고 가정하고 왼쪽 사람들에게만 초점을 맞춰서 번호를 갱신하자.

ex)

[0 0 0 2 0 1 6 7 6 9 ] 가 입력된다고 하자.

1번 사람은 왼쪽에 자기보다 작은 사람이 0명이므로 가장 큰 번호인 1을 부여한다. [ 1 ]

2번 사람은 왼쪽에 자기보다 작은 사람이 0명이므로 가장 큰 번호인 2를 부여한다. [ 1 2 ]

3번 사람도 마찬가지로 3을 부여하고 [ 1 2 3 ] 이 된다.

4번 사람은 작은 사람이 2명이므로 번호 3을 부여하고, 3보다 크거나 같은 번호를 하나씩 업시켜준다. [ 1 2 4 3 ]

5번 사람은 작은 사람이 0명이므로 가장 큰 번호인 5를 부여한다. [ 1 2 4 3 5 ]

6번 사람은 작은 사람이 1명이므로 2번 번호를 부여하고, 2번보다 크거나 같은 번호들은 하나씩 업시켜준다.

[1 3 5 4 6 2] 가 된다.

2. 왼쪽에 있는 사람의 수보다 나보다 작은 사람의 수가 더 큰 경우에는 "IMPOSSIBLE"을 출력하자.

ex)

[0 0 0 5  ~~ ]

4번 사람은 왼쪽에 3명밖에 없는데 작은 사람이 5명이므로 불가능한 경우다.

#include<cstdio>

int s[100] = {};
int r[100] = {};

int main(void) {
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int ninput, flag = 0;
		scanf("%d", &ninput);

		for (int j = 0; j < ninput; j++){
			scanf("%d", &r[j]);
		}

		for (int j = 0; j < ninput; j++) {\
			if (j < r[j]) {
				printf("IMPOSSIBLE\n");
				flag = 1;
				break;
			}

			s[j] = r[j];
			for (int k = 0; k < j; k++) {
				if (s[k] >= r[j])
					s[k]++;
			}
		}

		if (flag)
			continue;

		for (int j = 0; j < ninput; j++)
			printf("%d ", s[j] + 1);
		printf("\n");
		
	}
}

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 'Parenthesis' 문제를 다뤄보겠습니다.

대표적인 스택 자료구조를 이용한 문제로 쉽게 풀 수 있었습니다.

[문제해석]

주어진 문자열이 괄호가 제대로 짝이 맞는지 안 맞는지 판단해서 맞는다면 "YES" 아니라면 "NO"를 출력해라.

[알고리즘설계]

( ( ) ) ( ) ) 같은 경우는 앞에 4개 (  (  ) )  와 그 뒤 2개  ( ) 는 짝이 맞지만 마지막 ) 의 짝꿍이 없으므로 NO이다.

이처럼 우리는 지금 주어진 괄호가 짝궁이 있는지 없는지 판단하면 된다.

1. Stack 자료구조를 이용해서, ' ( ' 인 경우에는 Stack에 넣고, ' ) ' 인 경우에는 Stack에서 하나를 꺼내서 짝꿍을 맺어준다. 이때, ' ) ' 인 경우지만 Stack이 비어있다면 짝꿍이 없는 경우이므로 'NO'를 출력하고 또, 끝까지 진행했는데 아직 Stack에 남아있는 ' ( ' 가 존재해도 짝궁이 없는 경우이므로 'NO'를 출력한다. 이 외에는 "YES"를 출력해준다.

#include<iostream>
#include<stack>
#include<string>

using namespace std;

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

	int ninput;
	cin >> ninput;
	for (int i = 0; i < ninput; i++) {
		stack<int> list;
		string input;
		cin >> input;
		int flag = 0;
		for (int j = 0; j < input.length(); j++) {
			if (input[j] == '(')
				list.push(j);
			if (input[j] == ')') {
				if (list.empty()) {
					cout << "NO\n";
					flag = 1;
					break;
				}
				else
					list.pop();
			}
		}
		if (list.empty() && flag == 0)
			cout << "YES\n";
		else if (!list.empty() && flag == 0)
			cout << "NO\n";
	}
}

Stack 자료구조를 배울 때, 같이 배우는 대표적인 문제라 금방 해결할 수 있었습니다.

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다 보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실 분은 댓글로 자유롭게 남겨주셔도 좋을 것 같습니다! 
감사합니다.

안녕하세요.

여행벌입니다.

이번 포스팅에서는 ACM-ICPC 2012 예선전 D번 문제를 다뤄보겠습니다.

[문제해석]

어떤 숫자가 주어졌을 때, 그 수를 피보나치 수들의 합으로 표현해라. 이때, 가장 적은 개수의 합으로 표현해라.

[알고리즘설계]

1. 피보나치의 재귀식을 이용해 피보나치 수들을 먼저 배열에 구한다.

2. 피보나치 배열을 순회하며 주어진 숫자보다 작지만 가장 근접한 피보나치 수를 찾고, '주어진숫자 - 피보나치수'를 반복해주며, 이 수들을 저장한다.

3. 저장된 수들을 출력한다.

#include<cstdio>

int fibonachi_list[47] = { 0,1 };

int main(void) {
	for (int i = 2; i < 47; i++)
		fibonachi_list[i] = fibonachi_list[i - 1] + fibonachi_list[i - 2];
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int ninput;
		scanf("%d", &ninput);
		int count = 0, temp[100] = {};
		while (ninput) {
			for (int j = 0; j < 47; j++) {
				if (fibonachi_list[j] <= ninput && ninput < fibonachi_list[j + 1]) {
					temp[count] = fibonachi_list[j];
					count++;
					ninput -= fibonachi_list[j];
					break;
				}
			}
		}

		for (int j = 0; j < count; j++)
			printf("%d ", temp[count - 1 - j]);
		printf("\n");
	}
}

피보나치 수는 기존의 수들의 합으로 이루어졌기 때문에, 최소한의 개수를 이용하려면 단순히 큰 수부터 빼주면 된다.

피보나치 수가 아닌 어떤 임의의 수열이었으면, 문제가 어려웠을 것 같다.

열심히 공부하고 노력하고 있는 꿈 많은 예비 개발자입니다.
혼자서 공부한 내용을 정리하고 포스팅하다보니 틀린 내용이 있을 수도 있습니다.
많은 조언과 가르침 주실분은 댓글로 자유롭게 남겨주셔도 좋을것 같습니다! 
감사합니다.

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2012 예선전 문제인 'Canoe Racer' 문제를 다뤄보겠습니다.

[문제해석]

1. 특정 숫자 K 와 n 개 씩 4개의 숫자 배열이 주어졌을 때, 4개의 배열에서 하나씩 숫자를 뽑아 합했을 때, 특정 숫자 K과 가장 근접한 경우를 출력하라. (K과 가장 근접한 숫자가 2개 이상일 때는 더 작은 숫자를 출력하라.)

[알고리즘설계]

n 개 씩 4개의 숫자 배열을 각각 A,B,C,D 배열이라고 하자.

n이 최대 1000 이므로, A,B,C,D 배열에서 4중 for 문으로 1개씩 뽑아 모든 경우의 수를 다 구한다면, O(n^4)으로 당연히 시간 초과에 걸릴 것이다.

따라서, 우리는  A,B / C,D 배열을 2개씩 합쳐서 AB / CD 배열을 따로 만들고, 그 배열을 순회하며 답을 찾아줄 것이다.

또, AB배열을 순회하며, CD 배열에 있는 원소와의 합이 K와 근접한 숫자를 찾아야하는데, Linear Search 보다는 AB / CD 배열을 Sorting 한 후, Binary Search 를 이용해 답을 찾아줄 것이다.

그렇다면, O(n^4)의 복잡도가 O(n^2)으로 낮아진다.

#include<cstdio>
#include<algorithm>

int map[4][1000];

int ab[1000000];
int cd[1000000];

using namespace std;

int abs(int n) {
	if (n < 0)
		return -n;
	return n;
}

int main(void) {
	int test_case;
	scanf("%d", &test_case);

	for (int i = 0; i < test_case; i++) {
		int answer, ninput;
		scanf("%d %d", &answer, &ninput);

		for (int j = 0; j < 4; j++)
			for (int k = 0; k < ninput; k++) 
				scanf("%d", &map[j][k]);
		
		
		for (int j = 0; j < ninput; j++)
			for (int k = 0; k < ninput; k++){
				ab[ninput * j + k] = map[0][j] + map[1][k];
				cd[ninput * j + k] = map[2][j] + map[3][k];
			}

		sort(ab, ab + ninput * ninput);
		sort(cd, cd + ninput * ninput);


		int flag = 0, total_result = 999999999;
		int length = ninput * ninput;
		// Binary Search 
		for (int j = 0; j < length; j++) {

			int result = 999999999;
			int left = 0;
			int right = length - 1;

			while (left <= right) {
				int mid = (left + right) / 2;
				int temp = ab[j] + cd[mid];

				if (temp == answer) {
					printf("%d\n", answer);
					flag = 1;
					break;
				}
				else if (temp < answer) {
					left = mid + 1;
				}
				else{
					right = mid - 1;
				}

				if (abs(answer - result) > abs(answer - temp))
					result = temp;
				else if(abs(answer - result) == abs(answer - temp))
					result = min(result, temp);
			}

			if (flag)
				break;

			if (abs(answer - result) < abs(answer - total_result))
				total_result = result; 
			else if(abs(answer - result) == abs(answer - total_result))
				total_result = min(result, total_result);
		}
		if (flag)
			continue;

		printf("%d\n", total_result);
	}
}

배열을 2개씩 합쳐주면서 복잡도를 완전히 낮춰줄 수 있는데, 기존에 풀었던 문제와 유사해서 쉽게 문제를 해결할 수 있었다.