1463번
-
[DP] 1463번 문제풀이백준 문제풀이/Dynamic Programming 2019. 5. 4. 13:24
문제분석 문제는 이렇습니다. 임의의 숫자를 3가지의 연산을 이용하여 1을 만들고자 할때, 연산횟수의 최솟값은 ?! 1. X가 3으로 나누어 떨어지는 경우, 3으로 나눈다. 2. X가 2로 나누어 떨어지는 경우, 2로 나눈다. 3. X 에 1을 뺀다. 예를 들어, 12이라는 숫자가 주어졌고 같이 1로 만들어 봅시다. 첫번째 12 > 4 > 2 > 1 총 3회 두번째 12 > 6 > 3 > 1 총 3회 이런식으로 3가지의 연산을 사용하면 다양한 경우의 수가 등장합니다. 그러면 이 경우의 수를 모두 따져봅시다. d[i] = i 를 1로 만드는 최소 연산 횟수 라고 정의합시다. 1. x가 3으로 나누어 떨어지면, 3으로 나눈다. d[12] = d[12/3] + 1 ...더보기 현재, 12는 3으로 나누어 떨어지..