[Python] 백준 26595번 - '전투의 신' 풀이

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

26595번: 전투의 신

 

코드

import sys

N = int(sys.stdin.readline().strip())
A,P_a,B,P_b = map(int, sys.stdin.readline().strip().split())
result_x = 0
result_y = 0
for x in range(N//P_a + 1):
    y = (N - P_a*x) // P_b
    if A*result_x + B*result_y < A*x + B*y:
        result_x = x
        result_y = y
print(result_x, result_y)

이 문제에서 나오는 수식은 

A*x + B*y = 최대 

P_a*x + P_b*y <= N

두 개 입니다.

 

가장 먼저 해결해야 할 수식은 두번째 수식인 P_a*x + P_b*y <= N 입니다.

그러기 위해서 저는 for문을 이용하여 x와 y의 후보를 구했습니다.

그 과정에서 동시에 A*x + B*y 를 해결하도록 if문을 넣었습니다.

 

백준으로 코드를 테스트 하면서 시간초과가 가장 많이 떴는데요, 그를 해결하기 위해

A와 B를 비교하여 큰 수를 기준으로 먼저 계산하는 식으로 하려고 했습니다.

예를 들어

이렇게 입력했다고 한다면, B 가 더 큰 경우이므로

B의 수인 y를 먼저 계산하는 것입니다. 그래야 처음 말했던 두번째 수식(P_a*x + P_b*y <= N)에 들어가는 경우의 수가 좀 더 줄어들 수 있기 때문이죠. A를 먼저 계산한다면,

(0, 4), (1, 3), (2, 3), (3, 2), (4, 2), (5, 1), (6, 1), (7, 0), (8, 0) 으로 9개의 경우의 수가 나오는 반면에 B를 먼저 계산한다면,

(0, 4), (2, 3), (4, 2), (6, 1), (8, 0)  으로 5개의 경우의 수로 줄어듭니다.

 

하지만 코드 길이만 길어질 뿐이고 마찬가지로 시간 초과가 떴습니다.

 

구글링을 해보았는데, pypy3으로 실행한다면 시간초과를 해결할 수도 있다고 했습니다.

그러므로 pypy3으로 돌리면 코드가 성공적으로 돌아가는 것을 확인하실 수 있을 것입니다.

 

---

후기

돌아오는 데까지 너무 오래걸렸습니다. 좀 더 빨리 돌아오려고 했는데.. 팀플 하고 뭐하다 보니 너무 힘들어서 하기 싫더라고요.. 지하철에서 코드 짜기.. 그것도 불가능 했습니다... 출근 퇴근 시간의 지하철은... 정말 무섭네요.....

몇번이나 풀었는데 시간초과가 몇번이나 떴는지 모르겠습니다. 정답률이 30퍼센트 미만인 문제를 풀고 싶어서 그 중 끌리는 문제로 풀어보았습니다. 오랜만에 푸니까 재미있네요.