#1463 1로 만들기

💯 문제 → 숫자를 1로 만드는 것이 목표인 문제 ! 단, 3으로 나누거나 2로 나누거나 1을 빼는 연산만이 가능하며 연산의 횟수를 최소한으로 맞추어야되는 문제인 듯 !

<💭 방법>

🎈 1 동적계획법

• cache를 만들어 이 곳에는 각 수의 최소 연산 횟수를 저장한다.
• 3으로 나누어 지는 것을 기준으로 코드를 짜는데, 3으로 나누어 지지 않는 수들 중, 만약 1을 뺀 수의 연산 횟수와 2로 나눈 수의 연산 횟수를 비교하여 적용한다.

<😭 첫번째 코드>

cache = [0, 0, 1, 1]

for i in range(4, n+1):
    if i % 3 != 0 :
        cache.append(1 + cache[i-1])
        if i % 2 == 0 and cache[i-1] > cache[i//2]:
            cache[i] = 1 + cache[i//2]
    else:
        cache.append(1 + cache[i // 3])
        if cache[i-1] < cache[i//3]:
            cache[i] = 1 + cache[i-1]

안된 이유 : 일단 채점 82%에서 계속 틀렸다고 나오는 걸 보니, 아마 큰 수에서 문제가 있는듯 .. ㅠㅠ 그 수를 알려주면 좋겠다 .. 제발 ..내 생각엔 3으로 나누어 지지 않는 부분에서 2와의 비교가 없어서 그런 것 같고 3으로 우선순위를 정해놓고 문제를 풀어서 그런듯 !

🎈 2 동적계획법

• cache를 만들어 이 곳에는 각 수의 최소 연산 횟수를 저장한다.
• 2로 나누어 진 수와 3으로 나누어 진 수와 1을 뺀수의 최소 연산 횟수중 가장 작은 것을 골라 cache에 저장한다.

<🥰 첫번째 코드>

for i in range(4, n+1):
    temp = []
    if i % 3 == 0:temp.append(cache[i//3])
    if i % 2 == 0:temp.append(cache[i//2])
    if i-1 > 0: temp.append(cache[i-1])
    
    Min = min(temp)
    cache.append(Min+1)

<느낀점>
진짜 알고리즘 하나 잘못짜서 진짜 .. 무슨 일이냐 .. 이렇게 빨리 끝나는 코드를 ㅠㅠ 얼마나 잡고 있었던 거니 ㅎㅎ .. 정말 .. 여러가지의 방법을 생각해서 앞으론 알고리즘을 짜도록 하자 ..