[백준/Python] - 1463 1로 만들기

https://www.acmicpc.net/problem/1463

 

제출코드

N = int(input())
#연산횟수를 저장하는 memo
memo = [0] * (N+1)
for i in range(2,N+1):
    #이전값에서 1을 뺀 값을 연산횟수로 칭함
    memo[i] = memo[i-1] +1
    # i가 2로 나누어떨어지면(2를 1로만드는 최소 연산횟수를 구함)
    if i % 2== 0:
        memo[i] = min(memo[i], memo[i // 2] + 1)
    if i % 3 == 0:
        memo[i] = min(memo[i], memo[i // 3] + 1)
print(memo[N])

 

초기화 부분

 

memo = [0] * (N+1)

우리는 여기서 1부터 시작을 해야한다.

그러므로 1부터 10까지의 idx가 필요하다 그럼

0 1 2 3 4 5 6 7 8 9 10까지의 idx는 11개이다.

따라서 N+1로 둔다.

memo의 각 idx값의 뜻은 숫자 i를 1로 만드는데 필요한 연산 횟수이다.

→ 숫자 1을 1로 만드는 연산 횟수는? 1번 memo에 들어가게 된다.

    memo[i] = memo[i-1] +1
    # i가 2로 나누어떨어지면(2를 1로만드는 최소 연산횟수를 구함)
    if i % 2== 0:
        memo[i] = min(memo[i], memo[i // 2] + 1)
    if i % 3 == 0:
        memo[i] = min(memo[i], memo[i // 3] + 1)

이전 연산 횟수에서 1을 더한 값을 i번째 idx에 일단 넣는다.

그리고 i에 2를 나눈 나머지가 0이면 i에 2를 나눈값과 i번째 값을 비교해서 작은 값을 정한다.

 

EX

i 가 10일때를 예로 들어보자

i-1번째 즉, 9번째까지는 memo에 다 포함이 되어있다. 

memo = [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]
       #   1, 2, 3, 4, 5, 6, 7, 8, 9 ,10

해당하는 숫자를 1로 만들기까지 필요한 연산횟수이다.

10일때는 memo[i-1]번째 9번째값에서 1을 더한 값 3이 들어간다.

그리고 10이 2로 나눠지기때문에 5의 연산횟수와 9번째에서 3을 더한 값과 비교를 한다.

왜? 10은 9로 갈 수도 있고 5로 갈 수도있기때문에

거기에서 min값을 10에다가 넣는다.

---

어우 어렵네요....

뭔가 흐름은 전부 비슷한거 같은데