[ACM-ICPC][BOJ] 16702 - The Silence of the Lamp

안녕하세요.

여행벌입니다.

 

오늘은 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]을 진행해줍니다.

Volume	6	7	8	9	10	11	12	13	14
Count	1	1	2	2	3	3	5	5	6

15	16	17	18	19	20	21	22	23	24
7	8	8	10	10	12	13	14	14	18

#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로 정답에 다가가야 됨을 일찍 캐치했지만,

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

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

---