[백준] 2599번 짝 정하기

park geonwoo·2024년 10월 13일

목록 보기

21/32

https://www.acmicpc.net/problem/2599

문제 이해

문제 요약

학생 구성:
- 남학생과 여학생이 각각 N명씩 있으며, 총 3개 초등학교(A, B, C) 출신입니다.
- 각 초등학교별 남학생 수와 여학생 수가 주어집니다.
목표:
- 모든 남학생과 여학생을 짝지을 수 있는지 판단하고, 가능하다면 각 초등학교별로 짝의 수를 출력합니다.
- 짝짓기 규칙:
  - 짝을 이루는 남학생과 여학생은 서로 다른 초등학교 출신이어야 합니다.
  - 예를 들어, A초등학교 출신 남학생은 B초등 또는 C초등학교 출신 여학생과만 짝을 이룰 수 있습니다.
출력:
- 모든 학생을 짝지을 수 있다면: 1을 출력하고, 이어서 각 초등학교별로 짝의 수를 출력합니다.
- 짝짓기가 불가능하다면: 0을 출력합니다.

n = int(input())
school = []
check = True
for i in range(0, 3):
    x, y = map(int, input().split())
    school.append(x)
    school.append(y)

for i in range(0, school[0]+1):
    a = i
    d = school[0] - a
    e = school[5] - d
    b = school[2] - e
    c = school[1] - b
    f = school[4] - c

    if a >= 0 and b >= 0 and c >= 0 and d >=0 and e >= 0 and f >=0 :
        print(1)
        print(a, d)
        print(b, e)
        print(c, f)
        check = False
        break

if check:
    print(0)

입력 처리

입력 읽기:
```
n = int(input())
school = []
check = True
for i in range(0, 3):
    x, y = map(int, input().split())
    school.append(x)
    school.append(y)
```
- n: 남학생 또는 여학생의 수 (각각 N명).
- school: 6개의 요소를 갖는 리스트로, 순서대로 [A_m, A_f, B_m, B_f, C_m, C_f]를 저장합니다.
  - A_m: A초등학교 출신 남학생 수
  - A_f: A초등학교 출신 여학생 수
  - B_m: B초등학교 출신 남학생 수
  - B_f: B초등학교 출신 여학생 수
  - C_m: C초등학교 출신 남학생 수
  - C_f: C초등학교 출신 여학생 수

짝짓기 변수 설정

for i in range(0, school[0]+1):
    a = i
    d = school[0] - a
    e = school[5] - d
    b = school[2] - e
    c = school[1] - b
    f = school[4] - c

    if a >= 0 and b >= 0 and c >= 0 and d >=0 and e >= 0 and f >=0 :
        print(1)
        print(a, d)
        print(b, e)
        print(c, f)
        check = False
        break

변수 의미:
- a: A초등학교 출신 남학생이 B초등학교 출신 여학생과 짝을 이루는 수
- d: A초등학교 출신 남학생이 C초등학교 출신 여학생과 짝을 이루는 수 (a + d = A_m)
- e: C초등학교 출신 여학생 수 (C_f)에서 d를 뺀 값 (e = C_f - d), 이는 B초등학교 출신 여학생과 짝을 이루는 A초등학교 출신 남학생의 수
- b: B초등학교 출신 남학생 수 (B_m)에서 e를 뺀 값 (b = B_m - e), 이는 B초등학교 출신 남학생이 A초등학교 출신 여학생과 짝을 이루는 수
- c: A초등학교 출신 여학생 수 (A_f)에서 b를 뺀 값 (c = A_f - b), 이는 C초등학교 출신 남학생이 A초등학교 출신 여학생과 짝을 이루는 수
- f: C초등학교 출신 남학생 수 (C_m)에서 c를 뺀 값 (f = C_m - c), 이는 C초등학교 출신 남학생이 B초등학교 출신 여학생과 짝을 이루는 수
논리 흐름:
1. A초등학교 출신 남학생이 B초등학교 출신 여학생과 짝을 이루는 수 a를 0부터 A_m까지 반복.
2. d = A_m - a: A초등학교 출신 남학생이 C초등학교 출신 여학생과 짝을 이루는 수
3. e = C_f - d: C초등학교 출신 여학생 수에서 d를 빼면, A초등학교 출신 남학생 중 B초등학교 출신 여학생과 짝을 이루는 수
4. b = B_m - e: B초등학교 출신 남학생 수에서 e를 빼면, B초등학교 출신 남학생이 A초등학교 출신 여학생과 짝을 이루는 수
5. c = A_f - b: A초등학교 출신 여학생 수에서 b를 빼면, C초등학교 출신 남학생이 A초등학교 출신 여학생과 짝을 이루는 수
6. f = C_m - c: C초등학교 출신 남학생 수에서 c를 빼면, C초등학교 출신 남학생이 B초등학교 출신 여학생과 짝을 이루는 수
7. 모든 변수 a, b, c, d, e, f가 0 이상인지 확인:
  - 만약 모두 0 이상이라면, 유효한 짝짓기 방법을 찾은 것이므로 결과를 출력하고 종료
  - 그렇지 않다면, 다음 a 값을 시도
결과 출력:
```
if check:
    print(0)
```
- 모든 가능한 a 값을 시도했음에도 불구하고 유효한 짝짓기 방법을 찾지 못했다면, 0을 출력합니다.

예제 입력 1 분석

입력:

n = 6
school = [4, 2, 1, 3, 1, 1]
- A_m = 4, A_f = 2
- B_m = 1, B_f = 3
- C_m = 1, C_f = 1

반복 과정:

a = 0:
- d = 4 - 0 = 4
- e = 1 - 4 = -3 (음수, 불가능)
a = 1:
- d = 4 - 1 = 3
- e = 1 - 3 = -2 (음수, 불가능)
a = 2:
- d = 4 - 2 = 2
- e = 1 - 2 = -1 (음수, 불가능)
a = 3:
- d = 4 - 3 = 1
- e = 1 - 1 = 0
- b = 1 - 0 = 1
- c = 2 - 1 = 1
- f = 1 - 1 = 0
- 모든 변수 a=3, b=1, c=1, d=1, e=0, f=0이 0 이상이므로 유효
- 출력:
```
1
3 1
1 0
1 0
```

코드의 풀이 방법

제공된 코드는 브루트 포스(Brute Force) 방식과 알제브라적 접근을 결합한 형태로, 가능한 모든 a 값을 시도하여 유효한 짝짓기 방법을 찾습니다. 구체적인 풀이 방법은 다음과 같습니다:

초등학교별 학생 수 입력 및 저장:
- 3개 초등학교(A, B, C)의 남학생과 여학생 수를 school 리스트에 저장합니다.
짝짓기 변수 설정 및 계산:
- A초등학교 출신 남학생이 B초등학교 출신 여학생과 짝을 이루는 수 a를 0부터 A_m까지 반복합니다.
- 각 a 값에 대해 다음과 같이 다른 짝짓기 수를 계산합니다:
  - d = A_m - a: A초등학교 출신 남학생이 C초등학교 출신 여학생과 짝을 이루는 수
  - e = C_f - d: C초등학교 출신 여학생 중 A초등학교 출신 남학생과 짝을 이루지 못한 여학생의 수 (즉, B초등학교 출신 여학생과 짝을 이룰 남학생의 수)
  - b = B_m - e: B초등학교 출신 남학생이 A초등학교 출신 여학생과 짝을 이루는 수
  - c = A_f - b: A초등학교 출신 여학생 중 B초등학교 출신 남학생과 짝을 이루지 못한 여학생의 수 (즉, C초등학교 출신 남학생과 짝을 이룸)
  - f = C_m - c: C초등학교 출신 남학생이 B초등학교 출신 여학생과 짝을 이루는 수
유효성 검증:
- 계산된 모든 짝짓기 수 a, b, c, d, e, f가 0 이상인지 확인합니다.
- 만약 모두 0 이상이라면, 유효한 짝짓기 방법을 찾은 것이므로 결과를 출력하고 종료합니다.
짝짓기 불가능 시 처리:
- 모든 가능한 a 값을 시도했음에도 불구하고 유효한 짝짓기 방법을 찾지 못했다면, 0을 출력합니다.

코드의 알고리즘 및 자료구조

알고리즘

브루트 포스(Brute Force) + 알제브라적 접근:
- 3개의 초등학교 출신 남학생과 여학생을 기준으로 가능한 짝짓기 수를 계산하기 위해 반복문을 사용합니다.
- a 값을 0부터 A_m까지 시도하면서 다른 짝짓기 수(d, e, b, c, f)를 알제브라적으로 계산합니다.
- 각 단계에서 계산된 값이 모두 0 이상인지 확인하여 유효한 짝짓기 방법을 찾습니다.

자료구조

리스트(List):
- school: 6개의 요소를 가지는 리스트로, 각 초등학교별 남학생과 여학생 수를 저장합니다.
  - 인덱스:
    - 0: A초등학교 남학생 수 (A_m)
    - 1: A초등학교 여학생 수 (A_f)
    - 2: B초등학교 남학생 수 (B_m)
    - 3: B초등학교 여학생 수 (B_f)
    - 4: C초등학교 남학생 수 (C_m)
    - 5: C초등학교 여학생 수 (C_f)
변수:
- a, b, c, d, e, f: 각 초등학교별로 짝을 이루는 남학생과 여학생의 수를 저장하는 변수들
- check: 짝짓기 가능 여부를 추적하는 불리언 변수

시간 복잡도 분석

외부 반복문

범위: a는 0부터 A_m까지 반복합니다.
최악의 경우: A_m = 100,000
시간 복잡도: O(A_m) = O(100,000) → 선형 시간

내부 연산

각 a 값에 대해 d, e, b, c, f를 계산하고, 6개의 변수에 대해 0 이상인지 확인합니다.
시간 복잡도: O(1) (상수 시간)

전체 시간 복잡도

총 시간 복잡도: O(A_m) × O(1) = O(A_m) = O(100,000)

공간 복잡도 분석

리스트 school: 6개의 정수 → O(1) (상수 공간)
변수 a, b, c, d, e, f: 6개의 정수 → O(1) (상수 공간)
전체 공간 복잡도: O(1) (상수 공간)

코드의 정당성 및 한계

정당성

코드는 3개의 초등학교라는 고정된 수를 기반으로 작동합니다. 이를 통해 가능한 모든 짝짓기 수를 알제브라적으로 계산하고, 유효한 짝짓기 방법을 찾습니다. 이 접근 방식은 다음과 같은 이유로 정당합니다:

초등학교 수의 제한: 초등학교가 3개로 고정되어 있어, 변수의 수가 제한적입니다.
알제브라적 관계 설정: 각 짝짓기 수 간의 관계를 알제브라적으로 설정하여, 하나의 변수를 고정하면 다른 변수들을 계산할 수 있습니다.
완전 탐색: 가능한 모든 a 값을 시도하므로, 가능한 모든 짝짓기 방법을 탐색합니다.

한계

초등학교 수의 고정: 현재 코드는 3개의 초등학교에만 적용 가능합니다. 초등학교 수가 변할 경우, 코드가 동작하지 않습니다.
조건의 단순화: 알제브라적 접근은 특정 조건에서만 유효할 수 있으며, 더 복잡한 짝짓기 규칙이 있을 경우 확장하기 어렵습니다.
짝짓기 방법의 유일성: 여러 가지 유효한 짝짓기 방법이 있을 경우, 첫 번째로 발견된 방법만을 출력합니다. 특정 조건에 따른 최적의 방법을 찾지 않습니다.

park geonwoo

이전 포스트

[백준] 16947번 서울 지하철 2호선

다음 포스트