[BaekJoon] 백준 18868 멀티버스 1 (Python / 파이썬)

BaekJoon 백준 18868 멀티버스Ⅰ 문제는 M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을 때, 균등한 우주의 쌍이 몇 개인지 구하는 문제이다. 브루트 포스 알고리즘에 관한 문제로 난이도는 Bronze 1이다.

 

BaekJoon 18868 멀티버스Ⅰ 문제 정보

출처

- https://www.acmicpc.net/problem/18868

알고리즘 분류

- 브루트 포스 알고리즘 (brute force algorithm), 정렬

난이도

- 브론즈 1 / Bronze 1

 

멀티버스Ⅰ 문제 요약

• M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다.
• 행성의 크기를 알고 있을 때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다.
• 구성이 같은데 순서만 다른 우주의 쌍은 한 번만 센다.
• 두 우주 A와 B가 있고, 우주 A에 있는 행성의 크기는 A1, A2,..., AN, 우주 B에 있는 행성의 크기는 B1, B2,..., BN라고 하자.
• 두 우주의 행성 크기가 모든 1 ≤ i, j ≤ N에 대해서 아래와 같은 조건을 만족한다면, 두 우주를 균등하다고 한다.
  • Ai < Aj → Bi < Bj
  • Ai = Aj → Bi = Bj
  • Ai > Aj → Bi > Bj
• 2 ≤ M ≤ 10, 3 ≤ N ≤ 100, 1 ≤ 행성의 크기 ≤ 10,000
• 균등한 우주의 쌍의 개수를 출력한다.

 

문제 풀이 과정

1. 구성이 같고 순서만 다른 우주는 한 번만 세므로 서로 비교했던 우주, 행성끼리는 또 비교하지 않는다.
2. 중첩 for문을 사용하여 모든 우주의 모든 행성을 차례로 비교하면서 조건이 하나라도 만족하지 않으면 두 우주는 균등하지 않으므로 더 이상 비교하지 않는다.
3. 모든 조건이 만족하면 두 우주는 균등하므로 카운트한다.
4. 모든 우주끼리 비교가 끝나면 균등한 우주의 쌍의 개수를 출력한다.

 

코드 및 설명

• planets [][] - 각 우주의 행성들의 크기를 저장한 2차원 리스트
• ans - 균등한 우주의 쌍의 개수

# 행성의 조건 검사
def compare(p1, p2):
    for plnt1 in range(N):
        for plnt2 in range(plnt1 + 1, N):
            # 한 행성이라도 서로 다르면 비교 종료
            if p1[plnt1] == p1[plnt2]:
                if p2[plnt1] != p2[plnt2]:
                    return False
            elif p1[plnt1] > p1[plnt2]:
                if p2[plnt1] <= p2[plnt2]:
                    return False
            elif p1[plnt1] < p1[plnt2]:
                if p2[plnt1] >= p2[plnt2]:
                    return False
    # 모든 조건 만족하면 균등
    return True


M, N = map(int, input().split())
planets = []
ans = 0
for _ in range(M):
    planets.append(list(map(int, input().split())))
    
# 우주끼리 비교
for univ1 in range(M):
    for univ2 in range(univ1 + 1, M):
        # 행성끼리 비교
        if compare(planets[univ1], planets[univ2]):
            ans += 1
print(ans)

---

BaekJoon 백준 18868 멀티버스Ⅰ문제를 파이썬 브루트 포스 알고리즘 (brute force algorithm) python으로 풀어보았다. 난이도는 Bronze 브론즈 1이다.