난이도 ●◐○ l 풀이 시간 20분 l 시간 제한 1초 l 메모리 제한 128MB l 문제 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. ⓐ X가 5로 나우어떨어지면 5로 나눈다. ⓑ X가 3으로 나누어떨어지면 3으로 나눈다. ⓒ X가 2로 나누어떨어지면 2로 나눈다. ⓓ X에서 1을 뺸다. 정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 예를 들어 정수가 26이면 다음과 같이 계산해서 3번의 연산이 최솟값이다. 26 - 1 = 25 (ⓓ) 25 / 5 = 5 (ⓐ) 5 / 5 = 1 (ⓐ) 입력조건 첫째 줄에 정수가 X가 주어진다. ( 1

중복되는 연산을 줄이자 현실 세계에는 다양한 문제가 있다. 그런데 이중에서 컴퓨터를 활용해도 해결하기 어려운 문제는 무엇일까? 최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로도 해결하기 어려운 문제이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 이번 장에서 다루는 다이나믹 프로그래밍(Dynamic Programming) 기법으로 동적 계획법..