[파이썬/python] 백준 - 25551 멋쟁이 포닉스

문제

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

---

문제 설명

1. 포닉스는 흰색 또는 검은색의 마스크, 티셔츠, 바지만을 입는다.
   1. 마스크와 티셔츠는 다른 색이어야 한다.
   2. 티셔츠와 바지 역시 다른색이어야 한다.
   3. 이틀 연속으로 같은 색의 티셔츠를 입지 않는다.
   4. 한번 착용한 마스크, 티셔츠, 바지는 다시 사용하지 않는다.
2. 포닉스가 가진 각각의 개수가 주어질 때, 연속해서 옷을 고를 수 있는 최대 일수를 구하라.

 

---

풀이

포닉스가 가질 수 있는 옷의 종류는 검정과 흰색이다. 이를 W,B로 표현하자.

 

위에부터 순서대로 마스크, 티셔츠, 바지는 각각 연속해서 색이 겹치면 안되고, 최대 1회만 입을 수 있다.

 

그렇다면 나올 수 있는 조합은  (a) W-B-W or (b) B-W-B이다.

따라서 순서대로 개수가 주어지면 전체의 최소를 구하면 된다.

 

하지만 여러 예외가 존재한다.

 

(a)와 (b) 조합 둘 중 한 개의 어떤 옷(여기서 옷은 마스크, 티셔츠, 바지 중 1개를 말한다.)의 개수가 0개일 경우 그 조합은 선택할 수 없다. 즉 연속으로 조합을 번갈아가면서 입을 수 없기 때문에 결과는 1이다.

 

(a)와 (b) 조합 둘 모두 한 개의 어떤 옷의 개수가 0개일 경우 두 조합 모두 입을 수 없으므로 결과는 0이다.

 

둘 다 1개 이상의 옷이 있더라도 예외가 존재한다.

 

(a)와 (b) 조합의 개수가 동일하다면 (a) - (b) - (a) - (b) 순으로 입을 수 있다. 즉 $d1*2 or d2*2$가 정답이 된다.

 

(a)와 (b) 조합의 개수가 다르다면, 더 큰 쪽의 조합을 1번 더 입게 될 것이다. (a) - (b) - (a) - (b) - (a) 식으로 말이다.

즉 결과는 min(d1,d2) + 1이다.

 

1. 조건분기를 통해 결과를 도출한다.
2. d1 == d2일 때
   1. 조합을 만들 수 없으므로 0을 출력한다.
3. d1, d2 중 1개가 0일 때
   1. 1개의 조합만 입을 수 있으므로 1을 출력한다. 
4. d1과 d2가 1보다 크지만 동일할 때
   1. 둘 다 조합의 개수가 똑같으므로 d1*2 or d2*2를 출력한다. 
5. d1과 d2가 1보다 크거나 동일하지 않을 때
   1. d1,d2의 최솟값에 1을 더한 값을 출력한다.

---

코드

import sys
input = sys.stdin.readline

ma,mb = map(int,input().split())
ta,tb = map(int,input().split())
pa,pb = map(int,input().split())

d1 = min(ma,tb,pa)
d2 = min(mb,ta,pb)
if d1 + d2 == 0:
    print(0)
elif d1+d2 == d1 or d1+d2 == d2:
    print(1)
else:
    m = min(d1,d2)
    if d1 == d2:
        print(2*m)
    else:
        print(2*m+1)

---

시간복잡도

• 단준 조건분기로 문제를 풀이할 수 있다. 즉 시간복잡도는 $O(1)$이다.