굳건하게

안녕하세요.

여행벌입니다.

오늘은 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)으로 이 문제를 해결하는 방법에 대해서 다뤄보겠습니다.

안녕하세요.

여행벌입니다.

오늘은 ACM-ICPC 2014 본선 C번 문제인

BOJ 10448 Eureka Theorem 문제를 풀어보겠습니다.

[문제해석]

다음과 같은 Triangle Number로 이루어진 수열이 있을 때, 입력된 Input이 3개의 Triangular Number의 합으로 표현된다면 '1'을 출력, 아니라면 '0'을 출력하라.

[알고리즘설계]

1. N번 째, Triangular Number는 등비수열의 합 공식에 의해 n * (n + 1) / 2 로 구할 수 있다.

2. Input은 1000보다 작거나 같으므로, 우리는 1000보다 작거나 같은 Triangular Number만 미리 구해놓으면 된다.

3. Input이 작고, 1000보다 작거나 같은 Triangular Number도 44개밖에 없으므로 Brute 하게 3중 포문으로 구현한다.

#include<cstdio>

using namespace std;

int triangle_number[46] = { 0,1, };

int main(void) {
	for (int i = 2; i < 46; i++) {
		triangle_number[i] = i + triangle_number[i - 1];
	}

	int test_case;
	scanf("%d", &test_case);
	for (int i = 0; i < test_case; i++) {
		int ninput;
		scanf("%d", &ninput);
		int l, m, n, flag = 0;
		for (l = 1; l < 46; l++) {
			for (m = l; m < 46; m++) {
				for (n = m; n < 46; n++) {
					if (triangle_number[l] + triangle_number[m] + triangle_number[n] > ninput)
						break;
					if (triangle_number[l] + triangle_number[m] + triangle_number[n] == ninput) {
						printf("%d\n", 1);
						flag = 1;
						break;
					}
				}
				if (flag)
					break;
			}
			if (flag)
				break;
		}
		if (!flag) {
			printf("%d\n", 0);
		}

	}
}

Input이 작아서 무식하게 풀어도 되는 문제로 금방 해결할 수 있었습니다.

Triangle_number는 공식을 쓰기보다는 앞에서부터 쌓아가면 되므로 간단하게 구현할 수 있습니다.

안녕하세요.

여행벌입니다.

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

BOJ 11504번 Wheel of Numbers 문제를 다뤄보겠습니다.

[문제해석]

N개의 부분으로 나뉜 원판이 있고, 숫자 X와 Y가 있다고 하자. ( X와 Y의 자릿수는 같고, M이라고 하자.)

원판의 부분을 순서대로 { K1, K2, ⋯ , Kn } 이라고 했을 때, 임의의 Ki부터 시계방향으로 M개의 숫자를 읽었을 때, 이 숫자가 X와 Y의 사이에 있는 숫자가 되는 경우를 계산해주는 알고리즘을 구현하라.

[알고리즘설계]

X, Y는 1 ~ 9 자리 숫자 중 하나이고, 원판의 조각 수는 1 ~ 100 개다.

다라서, 가장 많은 연산을 요하는 경우는 원판이 100개로 나뉘고, X, Y가 9자리 숫자인 경우이다.

그래 봤자 우리는 각각의 경우에 대해서 9개씩만 앞으로 순회하며 세어주고, X 와 Y 사이에 있는지만 체크해주면 된다.

즉, 무식하게 풀어도 되는 문제이다.

1. Input을 받는다. 이때, X, Y는 우리가 원하는 형태가 아니라, 자릿수마다 숫자를 입력받으므로 우리가 원하는 정수 X, Y로 바꿔준다.

2. X, Y의 자릿수만큼 원판이 저장된 배열을 다 순회하며 X와 Y 사이에 있는 값을 세준다.

#include<cstdio>

using namespace std;

int x[9];
int y[9];
int list[100];

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

	for (int i = 0; i < test_case; i++) {
		// 입력받을게 참 많다...
		int ninput, length;
		scanf("%d %d", &ninput, &length);
		for (int j = 0; j < length; j++){
			scanf("%d", &x[j]);
		}
		for (int j = 0; j < length; j++){
			scanf("%d", &y[j]);
		}
		for (int j = 0; j < ninput; j++)
			scanf("%d", &list[j]);
		// X랑 Y를 int형으로 만들어주자.
		int X = 0, Y = 0, multiply = 1;
		for (int j = 0; j < length; j++) {
			X += x[length - 1 - j] * multiply;
			Y += y[length - 1 - j] * multiply;
			multiply *= 10;
		}
		int count = 0;
		// 순회하면서 count 해주자.
		for (int j = 0; j < ninput; j++) {
			int multiply2 = multiply / 10;
			int temp = 0;
			for (int k = 0; k < length; k++) {
				temp += list[(j + k) % ninput] * multiply2;
				multiply2 /= 10;
			}
			if (X <= temp && temp <= Y)
				count++;
		}
		printf("%d\n", count);
	}
}

예전 문제일수록 확실히 쉬운 것 같다.