[구현/수학] 백준 27939 가지 교배 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

27939번: 가지 교배

 

 

 

2. 문제 풀이

P-우선 교배: 흰색과 흰색을 교배하면 흰색이 되고, 그 외의 경우는 보라색이다.
W-우선 교배: 보라색과 보라색을 교배하면 보라색이 되고, 그 외의 경우는 흰색이다.

 

 입력으로 n개의 가지 품종의 색깔이 주어집니다.

 조수가 P-우선교배를 통해 품종을 먼저 개량하고, 개량된 품종을 교수가 W-우선 교배로 품종을 개량합니다. 이때 교수가 교배를 끝마친 후 흰색 가지를 얻을 수 있는지를 구해야 합니다.

 

 W-우선교배를 통해 교수가 흰색 가지를 얻으려면, 무조건 흰색 가지가 있어야 합니다.

 그러니 P-우선 교배에서 흰색이 나와야하고, 전체 표본 중에 흰색이 2개 이상이면 가능하다는 결론이 나옵니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
n = int(input())
kind = list(input().rstrip().split())
m, k = map(int, input().split())    # 조수와 품종의 수

assist = []
for _ in range(m):
    assist.append(list(map(int, input().split())))

# 조수들은 흰색이 2개 이상이어야 W 가능
# 교수는 흰색 한 1개라도 있어야 W 가능
for i in assist:
    white = 0
    for j in i:
        if kind[j-1] == "W":
            white += 1
    if white >= 2:
        print("W")
        break
else:
    print("P")

 하지만 위 코드는 틀렸습니다.

 "키위와 조수는 교배해서 나온 품종을 포함하여 품종이 하나만 남을 때까지, 현재 자신이 가지고 있는 품종 둘을 골라 교배하여 새 품종을 얻고, 사용한 품종은 버린다"

 위 문제는 계속 교배를 반복하기 때문에, P-우선교배에서 흰색만 나오기 위해서는 '흰색'만 가진 조수가 있어야 합니다.

 

 

import sys
input = sys.stdin.readline

# 입력
n = int(input())
kind = list(input().rstrip().split())
m, k = map(int, input().split())    # 조수와 품종의 수

assist = []
for _ in range(m):
    assist.append(list(map(int, input().split())))

# 조수들은 모두 흰색이어야 W 가능
# 교수는 흰색 한 1개라도 있어야 W 가능
for i in assist:
    for j in i:
        if kind[j-1] == "P":
            break;
    else:
        print("W")
        break;
else:
    print("P")

 따라서 흰색 가지만 가진 조수가 있다면 W를 출력하고, 없다면 P를 출력하면 됩니다.