1463 - 1로 만들기
📚 1463 - 1로 만들기
📖 풀이
그리디 알고리즘 : 내가 생각한 최적의 방법이 처음부터 끝까지 반례 없이 적용이 되는 경우
동적 계획법 : 가능성을 모두 두고 그 안에서 최솟값을 찾기
- 먼저 1을 더해준다. (이유는 먼저 더해도 어차피, 그 값이 2와 3으로 나누어지면 나누어진 값 중 최소 값으로 변경 가능하기 때문)
- 소스를 보면 쉽게 이해가 될 것이다.
소스
n = int(input())
dp = [0] * (n + 1) # dp에 초기값 0을 저장한다.
# bottom-Up 방식
# 2부터 n까지 dp 값을 구한다.
# 먼저 1을 더해준다. (이유는 먼저 더해도 어차피, 그 값이 2와 3으로 나누어지면 나누어진 값 중 최소 값으로 변경 가능하기 때문)
# 2에 n + 1까지
for cur_num in range(2, n + 1):
# 먼저 1을 더해준다.
dp[cur_num] = dp[cur_num - 1] + 1
# 3으로 나누어 떨어지는지 본다.
if cur_num % 3 == 0:
# 현재 값이 3의 배수라면 확인한다.
dp[cur_num] = min(dp[cur_num], dp[cur_num // 3] + 1)
# 2로 나누어 떨어지는지 본다.
if cur_num % 2 == 0:
# 현재 값이 2의 배수라면 확인한다.
dp[cur_num] = min(dp[cur_num], dp[cur_num // 2] + 1)
print(dp[n])
Author And Source
이 문제에 관하여(1463 - 1로 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@chang626/1463-1로-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)