Programming

[다이나믹 프로그래밍] ▲ 문제1 - 1로 만들기(217p)

[이코테] 문제1 - 1로 만들기(217p) (한줄평) 평소였으면 최소값을 구하는 문제니 BFS로 해결 했을테지만 전형적인 다이나믹 프로그래밍 문제! 추후 복습이 꼭 필요한 문제 풀이 시간: 40분 이내 1) 문제 해결 아이디어 정수 x가 주어졌을 때, 연산 4개를 적절히 사용해 1을 만드는데 사용되는 연산의 최솟값을 구하는 문제다. a. x가 5로 나누어 떨어지면, 5로 나눈다 b. x가 3으로 나누어 떨어지면, 3으로 나눈다 c. x가 2로 나누어 떨어지면, 2로 나눈ㄴ다 d. x에서 1을 뺀다 1. 최적 부분 구조 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제 해결O 2. 중복되는 부분 문제 동일한 작은문제를 반복적으로 해결해야 함 Q. 이 문제를 다이나믹 프로그래밍으로 ..