[1주차] 부족한 금액 계산하기

문제

 

새로 생긴 놀이기구는 인기가 매우 많아 줄이 끊이질 않습니다. 이 놀이기구의 원래 이용료는 price원 인데, 놀이기구를 N 번 째 이용한다면 원래 이용료의 N배를 받기로 하였습니다. 즉, 처음 이용료가 100이었다면 2번째에는 200, 3번째에는 300으로 요금이 인상됩니다.
놀이기구를 count번 타게 되면 현재 자신이 가지고 있는 금액에서 얼마가 모자라는지를 return 하도록 solution 함수를 완성하세요.
단, 금액이 부족하지 않으면 0을 return 하세요.

 

제한사항

• 놀이기구의 이용료 price : 1 ≤ price ≤ 2,500, price는 자연수
• 처음 가지고 있던 금액 money : 1 ≤ money ≤ 1,000,000,000, money는 자연수
• 놀이기구의 이용 횟수 count : 1 ≤ count ≤ 2,500, count는 자연수

---

풀이 방법

 

문제를 파악하고 바로 떠오른 해결방안은 반복문이다.

count까지의 for문을 사용하면 O(N)으로도 충분히 해결할 수 있다고 판단했다.

 

def solution(price, money, count):
   total = 0
   for c in range(1,count+1):
   	total += c * price
   answer = total - money
    
    if answer <= 0:
    	return 0
    else:
    	return answer

평균적으로 대부분의 테스트케이스를 0.10ms 안팎으로 해결할 수 있었다.

 

두번째로 떠오른 방법은 재귀적으로 푸는 방법이다.

for문에서 했던 c를 +1하면서 계산하는 것을 재귀적으로 하면된다.

다만, 종료조건으로 c가 문제에 주어진 count보다 크다면 그때의 놀이기구를 타는데에 드는 총 비용(result)를 return 해주면 된다.

import sys
sys.setrecursionlimit(100000) #파이썬 재귀횟수 제한 풀기

def solution(price, money, count):
    
    def totalMoney(c, result):
        #종료조건
        if c > count:
            return result
    	#진행
        result += price * c
        total = totalMoney(c+1, result)
        return total
    
    
    needMoney = totalMoney(1, 0) - money
    if needMoney < 0:
        return 0
    else:
        return needMoney

평균적으로 모든 테스트 케이스를 통과하는데 1ms 안팎으로 걸렸다.

---

결론

 

이번 문제의 난이도는 별로 어렵지 않았다. (개인적으로 Lv1 정도?)

그래서인지 재귀적으로 푸는 방법을 생각해내는 것도 그닥 어렵지 않았다.

다만, 이번 문제를 통해서 알게된 것은 재귀적으로 푼다고 해서 반복문보다 효율성이 좋다고 말할 수 없다는 것이다.

또한 파이썬은 RecursionError가 존재하기 때문에(백준,프로그래머스: 1000) 재귀를 사용할 때, 최대 재귀 깊이 제한을 풀어야한다.