ABC95 C - Half and Half에서 배운





생각해도 잘 모르고, 다음 페이지의 시작 부분, "AB 피자의 전체 탐색"이 보이고 핀 때였다.

제대로 읽지 않고, 떠오른 채 쓰면 다녔다.

halfandhalf.py
A,B,C,X,Y = map(int,input().split())

#X,Y 多い方 を 2 倍だけ AB ピザを用意できれば、
#worst case を加味して全探索したことがいえる 
N = 2*max(X,Y)
score = 0
ans = float("inf")
for n in range(N+1):
    cur = (n//2)
    if X-cur >= 0 and Y-cur>=0:
        score = n*C+(X-cur)*A+(Y-cur)*B
    elif X-cur < 0 and Y-cur>=0:
        score = n*C+(Y-cur)*B
    elif X-cur >= 0 and Y-cur <0:
        score = n*C+(X-cur)*A
    else:
        score = n*C

    if score < ans:
        ans = score
print(ans)

물론, 이하의 기술에서도 통과한다.

halfandhalf.py
A,B,C,X,Y = map(int,input().split())

ans = float("inf")
score = 0
#X,Y の最大値はそれぞれ 10**5 。
#その場合 AB ピザは 2 * 10**5 枚、最大で必要となる
#これがイメージ出来れば以下の記述でも対応可能
for i in range(1+2*10**5):
    if i%2 == 0:
        Z = i//2
        if X-Z >= 0 and Y-Z>=0:
            score = A*(X-Z) + B*(y-z) + C*i
        elif X-Z < 0 and Y-Z >= 0:
            score = B*(Y-Z) + C*i
        elif Y-Z < 0 and X-Z >= 0:
            score = A*(X-Z) + C*i
        else:
            score = C*i
    ans = min(ans,score)

print(ans)


다시 도전했습니다.
X, Y가 음수가되면 AB 피자의 전체 탐색
그렇다면 괜찮습니다.

자력으로 대답에 도착했습니다.
조금은 실력이 붙은 것 같아 기쁩니다.

abc95c.py
A,B,C,X,Y = map(int,input().split())

ab_cnt = 2*max(X,Y)
#print(ab_cnt)
ans = 10**100
for i in range(ab_cnt+1):
    if X-(i//2) < 0 and Y-(i//2) < 0:
        num = C*i
    elif X-(i//2) < 0 and Y-(i//2) >= 0:
        num = C*i+(Y-(i//2))*B
    elif X-(i//2) >= 0 and Y-(i//2) < 0:
        num = C*i+(X-(i//2))*A
    else:
        num = C*i+(X-(i//2))*A + (Y-(i//2))*B
    ans = min(ans,num)

print(ans)

좋은 웹페이지 즐겨찾기