[이것이코딩테스트다][MEMO] 10, 11강, 12강, 13강

 

강의 듣다가 필요한 부분은 메모를 하려 한다.

 

 

 

 

 

 

* 그리디 알고리즘에서 본 식인데

처음에 생각한 식이 모든 수를 탐색해서 -1을 한 뒤 결과를 도출해내는 방식이었다.

근데 그러면 시간 복잡도가 O(K) 인데

시간복잡도를 O(logK) 로 바꿀 수 있는 식이라 해서 메모한다.

 

 

 

(target 은 n을 k로 나눈 몫 * k 로 나머지 없는 수다.)

 

 

 

n, k = map(int, input().split())

result = 0

while n >= k:
    target = (n // k) * k
    result += (n - target)
    n = target
    result += 1
    n //= k
    
result += (n - 1)
print(result)

 

 

 

 

* 곱하기 혹은 더하기

 

data = map(int, str(input()))
result = 0

for d in data:
    if result == 0:
        result += d
    elif d == 0 or d == 1:
        result += d
    else:
        result *= d
        
print(result)