굳건하게

안녕하세요.

여행벌입니다.

이번 포스팅에서는 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개씩 합쳐주면서 복잡도를 완전히 낮춰줄 수 있는데, 기존에 풀었던 문제와 유사해서 쉽게 문제를 해결할 수 있었다.

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC Central European 본선 문제인

BOJ 16702 The Silence of the Lamps 문제를 풀어보겠습니다.

유럽문제라 그런지... 자주 안 쓰는 영단어들이 많이 보여서 문제 해석하는데 애를 먹었네요.

[문제해석]

-특정조건

1. square face가 없고, 즉 직육면체에서 어떤 면도 정사각형이 아니다.

2. 램프(lamp)의 부피가 주어진 부피를 넘지 않는다

위의 특정 조건을 모두 만족하는 직육면체(cuboid) 램프(lamp)를 부수는 이상한 사람이 있다.

램프(lamp)의 최대 부피가 주어졌을 때, 이상한 사람이 부수는 램프(lamp)의 수를 출력하라.

예를 들어,

부피 6이 주어지면 세 변의 길이가 (1,2,3) 인 경우를 제외하고 부피가 6보다 작거나 같으면서 정사각형이 생기지 않는 직육면체가 없습니다.

부피 7이 주어지면 부피 6에서 1,2,3을 일단 가져오고 정확히 부피가 7이면서 정사각형이 없는 직육면체를 만들 수 없으므로 마찬가지로 1개의 경우만 존재합니다.

부피 8이 주어지면 부피 7까지의 모든 경우의 수 (1,2,3)을 가져오고, (1,2,4) 경우가 하나 더 생기므로 2개의 경우가 존재합니다.

[알고리즘설계]

DP(Dynamic Programming)로 문제를 해결했습니다.

직육면체 3 변의 길이를 (x , y , z)라고 합시다.

x, y, z는 모두 달라야 정사각형이 생기지 않고, (1,2,3), (2,1,3) 등은 다 같은 램프로 취급하기 때문에,

우리는 x < y < z 인 경우만 신경을 써주면 됩니다.

먼저 x, y 를 1 , 2로 고정하면 z의 최솟값인 3부터, 즉 6부터 2칸씩 뛰어가면서 하나씩 카운트를 해줄 수 있습니다.

dp_list[6]++ dp_list[8]++ dp_list[10]++  ⋯

그다음으로는 x, y를 1, 3으로 고정하면 z의 최솟값인 4부터, 즉 12부터 3칸씩 뛰어가면서 카운트를 해줄 수 있습니다.

이런 식으로 나올 수 있는 모든 (x, y, z) 경우에 대해서 dp_list에 카운트를 진행하면,

dp_list[i] 는 x * y * z 가 i가 되는 모든 순간을 카운트하게 됩니다.

그리고 dp_list[i] 는 i보다 작은 dp_list에서 카운트된 값을 모두 가져올 수 있으므로,

다시 한번 순회하며 dp_list[i] += dp_list[i-1]을 진행해줍니다.

#include<cstdio>

int dp_list[1000001];

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

	int count = 0;
	for (int i = 1; i <= 99; i++) {
		for (int j = i + 1; j <= 999; j++) {
			int jump = i * j;
			int start = i * j * (j + 1);
			for (int k = start; k <= 1000000 ; k += jump) {
				dp_list[k]++;
				count++;
			}
		}
	}

	for (int i = 7; i <= 1000000; i++) {
		dp_list[i] += dp_list[i - 1];
	}

	for (int l = 0; l < test_case; l++) {
		int volume;
		scanf("%d", &volume);
		printf("%d\n", dp_list[volume]);
	}
}

Input이 test_case도 범위가 크고, Volume도 범위가 커서 DP로 정답에 다가가야 됨을 일찍 캐치했지만,

복잡도를 줄이기 위해서 되게 오랜 고민을 한 문제입니다.

다행히, 코드가 깔끔하게 나왔네요...!

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 본선 2011 문제인

BOJ 8901 Chemical Products 문제를 풀어보겠습니다.

[문제해석]

A, B, C 재료의 수가 주어지고, AB, BC, CA 화학 물질의 가격이 주어졌을 때, 최대로 얻을 수 있는 이익을 구하라.

[쓴이생각]

문제는 되게 간단하나, 풀이를 생각해내는데 1시간이 넘게 걸렸다.

처음에는 AB, BC, CA 를 만들 수 있는 모든 경우의 수를 3중 포문으로 순회하려고 했다.

최대 Input이 1000이므로, 10 ^ 9 (10억)번 연산이 필요하고, 당연히 시간 초과를 맛봤다...

AB, BC 의 갯수가 정해지면 CA는 남는 재료만큼 만들면 되므로 2중 포문으로 풀이가 가능하다는 것을 깨닫고, 문제를 해결할 수 있었다.

[알고리즘설계]

1. AB, BC 를 i , j 개씩 만들고 남은 재료로 CA를 최대한 만들어가며 Max 값을 구한다.

이때, AB가 i개 만들어진다면, B의 재료는 B - i 개 남아있으므로 고려해서 포문을 작성한다.

#include<cstdio>
#include<algorithm>

using namespace std;


int main(void) {
	int test_case;
	scanf("%d", &test_case);
	for (int i = 0; i < test_case; i++) {
		int A, B, C, AB, BC, CA;
		int max = 0;
		scanf("%d %d %d", &A, &B, &C);
		scanf("%d %d %d", &AB, &BC, &CA);

		for (int i = 0; i <= A; i++) {
			for (int j = 0; j <= B - i; j++) {
				// AB 를 i개 BC를 j개 만들었다고하자.
				if (C - j < 0)
					break;
				int temp = AB * i + BC * j + CA * (min(A - i, C - j));
				if (max < temp)
					max = temp;
			}
		}
		printf("%d\n", max);
	}
}

문제도 간단하고, 코드도 간단하지만 생각해내는데 1시간이 넘게 걸렸다...

백준에서 채점 현황을 보니 O(n^2)이 아닌 O(n)으로 푸신 분들이 종종 있는 것 같네요...

다들 괴물인 것 같지만...!

다음 포스팅에는 O(n)으로 이 문제를 해결하는 방법에 대해서 다뤄보겠습니다.