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

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LrsUaDxcDFAXc 

SW Expert Academy

 

1차 시도

문제를 처음 봤을 때는 가격을 리스트화한 후 max값과 max idx를 구한 후, for 문을 돌면서 cnt를 하나씩 증가시키고, cnt 값과 max를 구해서 매출을 구하고자 했다. 매출(ans)를 구한 후 tmp(물건을 살 때 잃는 손실의 합, tmp값은 ls값의 합으로 구함)를 빼서 총 이익을 계산하려고 했으나...

for 안에 while 안의 for문 안의 if가 너무 부담스러웠다.

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    ls = list(map(int, input().split()))
    maxP_idx = ls.index(max(ls))
    res = []
    cnt = 1
    if maxP_idx == 0:
        plus = 0
        print(tc, plus)
    else:
        tmp = 0
        while max(ls) != 0: #첫번째 값이 최대값이 아니라면 최대값 인덱스까지 구매하는 과정 의미
            for i in range(maxP_idx): #for문 돌면서 구매에 드는 비용 구하기
                tmp += ls[i]
            cnt += 1
            ls = ls[maxP_idx+1:]
            break

        ans = cnt * max(ls) #팔아서 얻을 수 있는 이익
        plus = ans - tmp #총 이익 : ans - tmp(구매에 드는 비용)
        res.append(plus)
        print(tc, plus, res)

#인덱스 이용해서 풀 것
#맥스까지 꾸준히 사고 맥스에서 팔고, 맥스 이후 원소들로 새로운 리스트 만들어서 맥스 구하고... 의 반복을 구현하고 싶음

2차 시도

최근  런타임 에러가 너무 자주 떴기 때문에... for문을 최대한 덜 돌고 싶어서 아이디어는 그대로 유지하고(앞에서부터 리스트를 보며 max값이 나오면 멈춰서고 max값까지의 손실과 팔면서 얻을 수 있는 이익을 계산한다 > 리스트를 줄여준다 > ...)

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    ls = list(map(int, input().split()))
    res = 0
    cnt = 1
    while len(ls) > 1 and ls.index(max(ls)) != 0:
        maxV =max(ls)
        idx = ls.index(maxV)
        loss = 0 #물건을 사는데 드는 돈
        loss_ls = [] #여러 개의 최대값이 나올 때까지 얻을 수 있는 loss list
        for i in range(idx):
            loss += ls[i]

        res += (max(ls) * idx - loss)
        ls = ls[idx + 1:]

    print(f'#{tc} {res}')

그러나 TC를 돌리는 과정에서 오류가 생겼다. 10개 중 6개가 맞아서 부분적으로 틀렸다는 것을 알 수 있었고...

ANS

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    ls = list(map(int, input().split()))
    res = 0
    cnt = 1
    if ls.index(max(ls)) == 0:
        print(f'#{tc} {res}')
    else:
        while len(ls) > 1:
            maxV =max(ls)
            idx = ls.index(maxV)
            loss = 0 #물건을 사는데 드는 돈

            for i in range(idx):
                loss += ls[i]

            res += (max(ls) * idx - loss)
            ls = ls[idx+1:]
        print(f'#{tc} {res}')

🔑

for-if-while-for 천국이기는 하지만 어쨌든 pass!
두번째 도전 코드의 문제는 while문의 조건이였다.

5
6426 9445 8772 81 3447
와 같은 TC를 돌려줄 때, 마지막 바로 위의 ls의 슬라이싱까지는 성공적으로 해서 [8772,81,3447]이 나옴을 알 수 있었다.

여기서 한 발 더 나가서 계속 while문을 돌려야 하는데 문제는 while문의 조건인
while len(ls) > 1 and ls.index(max(ls)) != 0:
ls.index(max(ls))가 0이 되어버려서 더이상 while문을 돌지 않는 것이다.
생각해보면 TC 중 하나인 '10 7 6'의 경우, 꾸준히 감소하기 때문에 이익을 낼 수 없는 것이다. max값의 인덱스가 0인 경우에 이익을 낼 수 없는 것이 아니다. max 인덱스가 0인 경우 이익을 낼 수 없다고 판단해서 문제를 풀어버려 while문이 잘 돌지 않았고, 문제를 더욱 어렵게 바라볼 수밖에 없던 것이다.

*ls의 슬라이싱이 왜 idx +1인지 잘 알아야 한다. idx면 최댓값을 같이 남기기 때문에 하면 idx으로 슬라이싱하면 안 된다!

+지금 생각하면 cnt 변수 선언할 이유가 없는데 왜 한 거지? 싶다. 이런 경우가 너무 많아서 TC 돌린 후 싹 주석처리 하거나 지우는 거 습관화해야지