My code
x = int(input())
d = [0] * 30001
for i in range(2, x + 1):
d[i] = d[i - 1] + 1
if i % 2 == 0 :
d[i] = min(d[i], d[i//2] + 1)
if i % 3 == 0:
d[i] = min(d[i], d[i//3] + 1)
if i % 5 == 0:
d[i] = min(d[i], d[i//5] + 1)
print(d[x])
Code Review
이번 문제는 다음과 같은 4 가지 연산을 수행하여 1을 만들 때 연산을 사용하는 횟수의 최솟값을 출력하는 문제였습니다.
-x 가 5로 나누어 떨어지면, 5로 나눈다.
-x 가 3으로 나누어 떨어지면, 3으로 나눈다.
-x 가 2로 나누어 떨어지면, 2로 나눈다.
-x 에서 1을 뺀다.
가장 먼저 문제를 해결 하기 위해 점화식을 생각해 보아야 합니다. 결론부터 먼저 말하자면 이 문제의 점화식은
a(i) = min[a(i-1), a(i/2), a(i/3), a(i/5)] +1
입니다. 점화식에 대해 설명하자면, 어떤 값 i 는 4가지의 연산으로 계산 가능한데, 4가지의 연산 중 가장 최소로 연산을 수행하는 방법을 택하여 주는 것 입니다. (1은 횟수를 구해야 하므로 더해주었습니다.)
따라서 먼저 연산 횟수를 저장할 배열 d 를 생성해줍니다. 그런 다음 2부터 입력한 정수 x + 1 까지 반복문을 수행해줍니다. 2부터 반복문을 수행하는 이유는 d[1] 은 계산해줄 필요 없이 0임을 이미 알고 있기 때문입니다.
먼저 현재 수에서 1을 빼는 경우를 구해줍니다. 만약 현재 수가 2, 3, 5 각각으로 나누어 떨어진다면 지금까지 구하여 현재 저장 된 최소 연산 횟수와, 배열 d 에 2, 3, 5 로 나눈 값 번째에 저장 된 연산 횟수를 비교하여 더 작은 값으로 갱신해줍니다. 이 과정을 모두 반복하면 원하는 최소 연산 횟수를 구할 수 있습니다.
댓글