1463번: 1로 만들기

Difficulty : Silver III

Problem Description

There is a number. You have to make this number to 1.

There are 3 ways to decrease the number.

1. If the number is divisible by 3, divide by 3.

2. If the number is divisible by 2, divide by 2.

3. decrease 1.

You can use many process to make 1.

The output is the smallest count to make 1.

 

Solution

As a result, all number must be divided into 2 or 3 as least 1 time except 1.

So I can calculate by use the divided value that was already calculated before.

 

N is for input and arr is for count. There are four numbers to set the initial value.

 

Calculate the count of numbers from 4 to N.

First, input 0 to avoid index error.

All I is constructed to a*3 + remainder, b*2 + remainder.

Calculate the remainder by dividing i into 3 and 2.

And the last '+1' means the count of process to divide number.

 

Today's English

divisible by x : x로 나누어 떨어지다

 

여담

다이나믹 프로그래밍 태그가 붙은 문제만 풀고 있는데 골드 5 난이도만 시도해 보니 문제가 너무 안풀렸다.

요즘 3일에 글을 한번씩 올린 이유도 문제가 안풀려서 계속 시도해 보느라 오래 걸린 것이다.

인정할 건 인정하고 DP는 실버 수준부터 차근차근 해보도록 하겠다.(실3도 어려워서 3개만에 찾은...)