#2839 설탕배달

💯 문제 → 정수 n을 1, 2, 3의 합으로 나타내는 총 경우의 수를 구해야 되는 문제 ! 순서도 생각해 줘야함

<💭 방법>

🎈 1 동적계획법, 그리디를 사용하는 방법

• 일단 먼저 3과 5으로 나누어 지지 않는 N일 경우 -1을 출력하게 만들어준다.
• 그리디 알고리즘을 사용하여 가장 최소한의 봉지로 배달을 해야되므로 5로 먼저 나누어 준다.
• 나누고 난 나머지가 만약 3으로 나누어 지지 않거나, 5로 나누어 지지 않으면 나눈 봉지라고 생각하지 않는다.

<😥 첫번째 코드>

def Sugar(n):
    if n % 5 == 0:
        sugar += n // 5
        return sugar
    
    elif n % 3 == 0:
        sugar += n // 3
        return sugar

    else:
        if (n // 5) > 0:
            sugar += 1
            n -= 5
            return Sugar(n)
        
        elif (n // 3) > 0:
            sugar += 1
            n -= 3
            return Sugar(n)

        else:
            return -1

안된 이유 : 18같은 경우에는 5+5+5+3으로 계산하여 총 4가지의 수가 나와야 하지만, 먼저 3과 5로 나누어 지는 수를 먼저 처리해 주었기 때문에 6으로 경우의 수가 나오게 됨.

🎈 2 동적계획법, 그리디를 사용하는 방법

• 일단 먼저 1 ~ 5까지의 경우의 수를 저장을 한다.
• 그리디 알고리즘을 사용하여 가장 최소한의 봉지로 배달을 해야되므로 5에 대한 경우의 수를 생각해주고 다음으로 3에 대한 경우의 수를 생각해주기로 한다.
• 계산을 해보니 결국 전에 계산되었던 결과를 사용하는 경우가 있었기 때문에 그 계산 결과 경우의 수와 나눈 경우의 수를 이용하여 계산한다.
• 만약 5를 이용하여 경우의 수를 구할 수 없는 경우에는 3의 배수인지 확인 후 배수가 맞다면 그 값으로 바꾸어 준다.

ex) 8과 13, 18의 경우
8 = 5 + 3 → 1 + 1
13 = 5 + 8 → 1 + 2 (8의 경우의 수를 이용함)
18 = 5 + 13 → 1 + 3 (13의 경우의 수를 이용함)

<🥰 첫번째 코드>

def Sugar(n):
    cache = [-1, -1, -1, 1, -1, 1]

    for i in range(6, n+1):
        cache.append(1 + cache[i-5])

        if cache[i] == 0:
            cache[i] = -1
        
            if i % 3 == 0:
                cache[i] = i // 3

    return cache[n]

<느낀점>
진짜 너무 안풀려서 마치 뫼비우스의 띠에 들어온 것 같은 느낌이 들었다 .... 진짜 .... 풀어도 풀어도 하나 고치면 하나 틀리고 .... 진짜 나름 시간이 많이 들었던 문제였다 ... 다른 분들의 풀이를 참고하고 싶었지만, 동적 계획법을 사용하여 문제를 해결하신 분들의 풀이를 찾지 못하여 ㅠㅠ 결국 나혼자 전전긍긍 .. 하면서 풀었던 문제 ! ,, 다음날 일어나서 다시 찬찬히 생각해보니 어제 왜그렇게 풀었나 싶을 정도로 빨리 풀렸던 문제 .. ㅎ .. 이제 이런 문제 두렵지 않아 ..