[파이썬(python)] 이것이 취업을 위한 코딩테스트다 1로 만들기

이 문제는 다이나믹 프로그래밍을 연습하기위해 푼 문제다.

처음 작성한 코드는 아래와 같은데, 나중에 d 배열을 출력할 때

7, 11, 13, 17 등 소수에 대해서만 0값이 출력된다는 문제가 있다.

n에 대한 값은 정확히 출력된다.

 

아. 밑의 코드는 d[n]만 정확히 구하기 위한 함수로서, 7, 11, 13 등의 소수는 호출되지 않는다.

 

그렇다면 반복문을 이용하여 1~n에 대해 모두 정확히 구하려면 코드를 개선해야한다.

 

x = int(input())

d = [0] * (x+1)

def mincount(n):
    if n == 1:
        return 0

    if d[n] != 0:
        return d[n]

    if n % 5 == 0:
        d[n] = min(mincount(n//5) + 1, mincount(n-1) + 1)
        return d[n]
    if n % 3 == 0:
        d[n] = min(mincount(n//3) + 1, mincount(n-1) +1)
        return d[n]
    if n % 2 == 0:
        d[n] = min(mincount(n//2) + 1, mincount(n-1) + 1)
        return d[n]

    return mincount(n-1) + 1

print(mincount(x))

 

코드 개선

반복문을 활용하여 작은수부터 배열을 채워나가면 빠뜨리는 수 없이 정확히 x값까지 계산할수있다!

 

 

x = int(input())

d = [0] * (x+1)

for i in range(2, x+1):
    if i % 5 == 0:
        d[i] = min(d[i//5] + 1, d[i-1]+1)
        continue
    if i % 3 == 0:
        d[i] = min(d[i//3]+1, d[i-1]+1)
        continue
    if i % 2 == 0:
        d[i] = min(d[i//2]+1, d[i-1]+1)
        continue

    d[i] = d[i-1] + 1

print(d)

 

답지를 보고 개선한 코드

이렇게 하면 같은 코드를 줄일수있다.
 

x = int(input())

d = [0] * (x+1)

for i in range(2, x+1):
    d[i] = d[i-1] + 1
    
    if i % 5 == 0:
        d[i] = min(d[i//5] + 1, d[i])
        
    if i % 3 == 0:
        d[i] = min(d[i//3] + 1, d[i])
        
    if i % 2 == 0:
        d[i] = min(d[i//2] + 1, d[i])

print(d)