[코테/Python] 도형 만들기

목차 (OPEN)

• 📑 문제
• 🔎 조건 분석
• 💡 아이디어
• 👩🏻‍💻 전체 코드
• 📚 결론

 

 

 

 

📑 문제

• 서로 다른 막대기 n개가 주어진다.
• 각 막대기의 길이는 a1, a2, ..., an 이다.
• 이 중 3개 이상의 막대기를 골라 넓이가 0이 아닌 단순 다각형을 만들 수 있는 경우의 수를 구해야 한다.
• 경우의 수는 매우 클 수 있으므로 10^9 + 7 로 나눈 나머지를 출력한다.

 

 

---

🔎 조건 분석

이 문제는 꽤 어려워서 시간을 많이 투자했던 만큼 ,,

조건 분석부터 하고 시작해보려 한다.

 

 

우리가 단순 다각형을 하나 그렸다고 생각하자.

가장 긴 변의 길이를 Lmax , 나머지 변들의 합을 Srest 라 해보자.

 

이제 다각형에서 Lmax의 양 끝 점을 A, B라 두고,

나머지 변들만 따라서 A에서 B까지 걸어가는 상황을 상상해보자.

당연히 이 경로의 길이는 나머지 변들의 합인 Srest 일 것이다.

 

 

삼각부등식에 의해, 어떤 경로로 두 점 A, B 를 잇든간에 AB의 직선 거리 <= 경로의 길이 여야 한다.

그리고 여기서 말하는 AB의 직선 거리가 바로 Lmax 이고, 경로 길이가 Srest 이므로,

Lmax <= Srest 라는 조건이 만들어진다.

 

 

 

그런데 만약, Lmax == Srest 라고 해보자.

그러면, AB를 잇는 막대기 외에 나머지 모든 막대기들을 한줄로 쭉 펼쳐놔야지만 길이가 맞게 된다.

 

 

그러나 우리는 넓이가 0이 아닌 다각형을 원하기 때문에

조건을 Lmax < Srest 로 바꿔주어야 한다.

 

 

 

 

 

자 그럼 이제 식을 살짝 변형해보려고 한다.

 

집합 S의 전체 합은 sum(S), 이중에서 가장 긴 변을 max(S)라고 부르면,

나머지 변들의 합은 전체 합 sum(S)에서 가장 긴 변 max(S)를 뺀 값이 될 것이다.

즉, 나머지 변들의 합 Srest = sum(S) - max(S) 이다.

 

이제 다시 정리해보면 다각형의 조건은

위에서 말했던 Lmax, 즉 지금의 max(S)가 Srest, 즉 지금의 sum(S) - max(S) 보다 작아야 했으므로,

max(S) < sum(S) - max(S) 라고 할 수 있다.

 

이거를 식을 조금만 깔금하게 정리해주면,

2 * max(s) < sum(S) 로 바꿀 수 있다.

 

 

---

💡 아이디어

위의 조건 분석을 통해 우리는

선택한 막대 집합 S에서 2 * max(S) < sum(S) 일 때만 넓이가 0이 아닌 다각형을 만들 수 있다는 사실을 알게 되었다.

 

이제 남은 문제는 모든 가능한 부분 집합을 어떻게 효율적으로 셀 것인가이다.

 

 

 

그러기 위해서는 먼저, 막대기들을 오름차순으로 정렬해줘야 한다.

이렇게 하면, 인덱스가 뒤로 갈수록 막대 길이가 길어지므로, 가장 긴 막대기를 고정하기가 쉬워지기 때문이다.

예를 들어, i번째 막대기를 가장 긴 막대기로 선택했다면,

앞쪽의 막대기들만 고려해서 부분집합을 만들어주면 되는 것이다.

 

 

 

다음으로는, 임의의 다각형 집합을 잡았을 때,

결국 그 집합의 성립 여부는 가장 긴 막대기 하나에 의해서 결정되는 것이다.

따라서 가장 긴 막대기를 하나씩 고정하고, 그보다 짧은 막대기들 중 일부를 골라 조건을 만족하는지 확인해주면 된다.

 

예를 들어, i번째 막대기를 가장 긴 막대기로 고정했다고 하자.

그러면 후보 집합의 총 개수는, i개의 막대기 중 아무거나 고르는 부분집합의 수와 같다.

(단, 공집합과 크기가 1인 집합은 다각형을 만들 수 없으니 빼줘야 한다.)

이 경우 총 후보의 개수는 2^i - 1 - i 가 된다.

(-1은 공집합을 빼준 것이고, -i는 크기가 1인 집합의 개수를 빼준 것이다.)

 

 

 

이제 문제의 핵심인데, 조건을 만족하지 못하는 집합을 세어주면 된다.

아까 문제 조건을 만족하는 조건이 2 * max(S) < sum(S) 라고 했으니까,

만족하지 못할 조건은 2 * max(S) >= sum(S) 가 될 것이다.

 

그럼 이제 이 개수를 세야 하는데,

단순히 부분집합을 하나씩 만들어서 합을 계산하게 되면

시간 복잡도가 O(2^n) 이어서 절대 불가능하다 ..🤧

 

 

 

그래서 이용해주는 것에 DP이다.

나는 아래와 같이 나눠주었다.

• dp1[x] 👉🏻 합이 정확히 x이면서 부분 집합의 크기가 1인 부분 집합의 개수
• dp2[x] 👉🏻 합이 정확히 x이면서 부분 집합의 크기가 2 이상인 부분 집합의 개수

 

이렇게 나누는 이유는,

다각형이 되려면 최소 3개 이상의 막대기가 필요하기 때문이다.

 

따라서 새로운 막대기를 추가할 때 아래의 과정을 거치게 된다.

• 기존의 크기가 2 이상인 집합에 막대기를 추가하면, 여전히 크기가 2 이상이므로 dp2에 더해준다.
• 기존의 크기가 1인 집합에 막대기를 추가하면, 크기가 2 이상으로 승격하므로 dp2에 더해준다.
• 막대기 하나만 단독으로 추가하면, dp1에 더해준다.

 

위의 과정을 반복하면,

현재까지 고려한 막대기들로 만들 수 있는 부분집합의 합 분포를 DP 배열에 모두 기록할 수 있다.

 

 

---

👩🏻‍💻 전체 코드

MOD = 10**9 + 7

n = int(input())
A = list(map(int, input().split()))
A.sort()

Amax = max(A)
ans = 0

# 부분 집합의 개수를 관리하는 DP 테이블
dp1 = [0] * (Amax + 1) # 크기가 1인 집합
dp2 = [0] * (Amax + 1) # 크기가 2 이상인 집합


# 2^i 미리 계산해두기
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
	pow2[i] = (pow2[i - 1] * 2) % MOD


for i, x in enumerate(A):
	# i번째 막대기를 가장 긴 막대기로 정했ㅇ르 때, 가능한 모든 부분집합의 개수
	total = (pow2[i] - 1 - i) % MOD

	# 조건을 만족 못하는 부분집합의 개수 세기
	delete = 0
	jsum = 0
	for j in range(0, x + 1):
		jsum = (jsum + dp2[j]) % MOD
	delete = jsum


	ans = (ans + (total - delete)) % MOD

	# 새로운 막대기 추가 시 DP 갱신
	l = x
	for k in range(Amax - l, -1, -1):
		if dp2[k] or dp1[k]:
			dp2[k + l] = (dp2[k + l] + dp2[k] + dp1[k]) % MOD

	# dp1도 갱신해주기
	if l <= Amax:
		dp1[l] = (dp1[l] + 1) % MOD



print(ans % MOD)

 

 

 

---

📚 결론

개인적으로 DP 문제다 보니까 뭐 아이디어 떠올리는게 젤 어려웠을 것 같아서

내가 생각한 아이디어를 구체적으로 적다 보니 글이 꽤 길어져 버렸다 ..😅

 

이 문제는 단순 조합으로 풀면 경우의 수가 너무 커서 시간 초과가 발생하므로,

가장 긴 막대기를 고정한 뒤, 나머지 부분집합의 합을 DP로 관리하는 것이 핵심이었다.

 

이 방법으로 풀면 O(n * Amax) 정도의 복잡도로 문제를 해결할 수 있고,

다각형 성립 조건을 부분집합 합의 분포를 활용해서 효율적으로 판별할 수 있다.

 

진짜 이 문제 풀다가 너무 스트레스 받아서 4번 문제는 보지도 않고 빡종할 뻔 했는데,

그래도 풀고 나니까 쾌감은 짱인 것 같다 ,,ㅎㅎ

오랜만에 코테 문제 풀려니까 머리가 잘 안 돌아갔어서

앞으로는 종종 코테 문제들 푸는 시간을 다시 가져야겠다 ,,😭😭