1463. 1로 나누기 (열흘 전과 코드 비교)

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

 

 

 

열흘 전... (인터넷에서 보고 따라한 코드)

n = int(input())
m = []  # 미리 초기화를 하면 밑부분 m[0]~m[3]을 초기화해주는 부분에서 out of index 날 수 있다
 
m.append(0)
m.append(0)
m.append(1)
m.append(1)
 
for i in range(4, n+1):
    m.append(m[i-1] + 1);
    if(i % 2 == 0):
        m[i] = min(m[i], m[i//2] + 1) 
    if(i % 3 == 0):
        m[i] = min(m[i], m[i//3] + 1) 
 
print(m[n])

 

 

이번에 풀이법이 생각나지 않을 무렵 직접 작성한 코드

import sys

N = int(sys.stdin.readline())
cal = [0 for _ in range(N+1)]  # 0은 없는 셈 친다.

if N > 1:
    cal[2] = 1  # cal[1] = 0

for i in range(3, N+1):
    tmp1 = i - 1
    tmp2 = i // 2
    tmp3 = i // 3

    if i % 2 == 0 and i % 3 == 0:
        cal[i] = min(cal[tmp1], cal[tmp2], cal[tmp3]) + 1
    elif i % 2 == 0:
        cal[i] = min(cal[tmp1], cal[tmp2]) + 1
    elif i % 3 == 0:
        cal[i] = min(cal[tmp1], cal[tmp3]) + 1
    else:
        cal[i] = cal[tmp1] + 1

print(cal[N])

 

시간이 100ms가 더 오래 걸렸지만, 유의미한 차이는 아닌듯하다.

하지만 코드를 봤을 때 확실히 다른데서 가져온 코드가 깔끔해보인다.

전자가 보고 따라한 코드(한마디로 퍼온 코드), 후자는 직접 작성한 코드이다.

 

가장 먼저, 기저 사례를 정의하는 부분이 다른데, 

전자의 경우 append를 이용해 out of index가 안나게끔 정의해준 반면

후자의 경우 2 이상일 경우에만 2를 정의하도록 했다. 사실 처음에는 if문이 없었는데, 자주 하는 실수이다.

문제에서 N이 어디부터 주어질 수 있는지 보지 않은 것이다.

문제에서는 1부터 주어질 수 있다고 했으므로, N이 1일 때도 고려해야한다.

무턱대고 cal[2]부터 정해주면 N이 1일 때 out of index 오류가 난다.

 

전자는 왜 하필 4부터 for문을 돌렸는지 의문이다. 직접 계산한 가능 범위라면, 5도 될 수 있고 6도 될 수 있지 않나 싶다.

후자는 3부터는 일반화된 수식이 적용될 수 있다는 생각이 들어 바로 3부터 for문을 돌렸다.

 

이제 for문 내부를 보자.

전자는 일단 N-1했다고 치고 그 값을 리스트에 넣고 N / 2 가 가능하다면 그 중 최솟값을 다시 넣고, N / 3이 된다면 그 중 최솟값을 다시 넣고, N / 2 와 N / 3 이 둘다 된다면 그 중 최솟값으로 또다시 수정했다.

후자는 N-1, N / 2, N / 3 한 값을 따로 구해서 그 값 중 최솟값을 넣었다.

 

보기에는 전자의 코드가 훨씬 깔끔해보이지만 시간 차이가 크지 않아 유의미한 차이는 없어보이고,

중요한 것은 열흘 전에 이 문제를 풀 때는 바텀업이 어쩌고 재귀가 어쩌고 했던 반면,

이번에 풀 때는 동적 프로그래밍이니 값을 저장해주면서 이건가...? 하고 쉽게 풀어갔다는 점에 의미가 있겠다.