[SWEA, Python] 백만 장자 프로젝트

정답 코드 

t = int(input())
for tc in range(1, t+1):
    ans = 0
    n = int(input())
    price = list(map(int, input().split()));
    while len(price) != 0:
        max_idx = price.index(max(price))
        cal = price[:max_idx]
        for i in range(len(cal)):
            ans += abs(price[max_idx] - price[i])
        price = price[max_idx+1:]
    print(f'#{tc}', ans)

풀이 과정 

1. dfs 재귀로 시도 -> 실패(시간초과)

def dfs(idx, benefit, cost):
    global n, price, ans
    if idx == n:
        ans = max(benefit, ans)
        return
    all_sold = benefit + len(cost)*price[idx]
    for c in cost:
        all_sold -= price[c]
    #팔았을 때
    dfs(idx+1, all_sold, [])
    #팔지 않았을 때
    dfs(idx+1, benefit, cost + [idx])

t = int(input())
for tc in range(1, t+1):
    ans = 0
    n = int(input())
    price = list(map(int, input().split())); arr = []
    dfs(0,0, arr)
    print('#{} {}'.format(tc, ans))

최근 dfs에 꽂혀서 문제를 보자마자 dfs로 풀어버렸더니 입력이 1000,000이라 시간 초과가 났습니다. 

2. 구현 -> Fail. 10개중 6개 정답 

t = int(input())
for tc in range(1, t+1):
    ans = 0
    n = int(input())
    price = list(map(int, input().split()));
    while len(price) != 0:
        max_idx = price.index(max(price))
        if max_idx == 0:
            break
        cal = price[:max_idx]
        for i in range(len(cal)):
            ans += abs(price[max_idx] - price[i])
        price = price[max_idx+1:]
    print(f'#{tc}', ans)

위와 같이 max값을 찾아 리스트를 슬라이싱하고, 앞의 price값들의 차를 더해주는 방식으로 구현했습니다.

하지만, 10개중 6개만 맞았고 디버깅 끝에 반례를 발견했습니다.

만약 10, 1, 6 과 같은 입력이 들어오면, 최대 이익인 5를 출력해야 합니다. 하지만 현재 제 코드는 max_idx를 구했을 때, max_idx가 0이 되므로 break가 되어 0을 출력하고 있었습니다. break문을 삭제한 후, 통과했습니다.