동적 계획법
-
[다이나믹 프로그래밍] 문제 이름 : 1로 만들기Algorithm/유형별 문제 풀기 2021. 11. 24. 12:06
문제 설명 정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지 이다. 1. X가 5로 나누어떨어지면, 5로 나눔 2. X가 2로 나누어떨어지면, 2로 나눔 3. X가 3으로 나누어떨어지면, 3으로 나눔 4. X에서 1을 뺌 정수 X가 주어졌을 때, 위의 연산 4개를 적절히 사용해 1을 만들려고 한다. 연산을 사용하는 횟수의 최소값을 구하시오. 사용 개념 다이나믹 프로그래밍, 보텀업 방식 문제 해결 아이디어 모든 연산 가능 경우에 대해 생각해봐야 할 것 같은데 너무 많은 것 아니야..? → 맞아! 경우의 수로 모든 경우에 대해 봐야되는거 맞는데 다이나믹 프로그래밍을 사용해서 빠르게 구하는거지! 어차피 최소 연산 횟수 구하는 것이니까! 1. 함수 호출 과정 도식화하기 → 모든 경우의 ..