ynamic Programming - 예제
1로 만들기
이코테 책 217p
문제
- 시간제한
- 1초
- 입력
- 정수 X (1<=X<=30,000)
- 출력
- 연산을 하는 횟수의 최솟값
- 문제 요약
- 주어지는 정수 X에게 사용 가능한 연산은 4가지
- X가 5로 나누어떨어지면, 5로 나눔
- X가 3로 나누어떨어지면, 3로 나눔
- X가 2로 나누어떨어지면, 2로 나눔
- X에서 1을 뺌
- X가 주어지면 연산 4개를 적절히 사용해서 1만드려고 함. 연산 사용하는 횟수의 최솟값 출력하시오.
- 주어지는 정수 X에게 사용 가능한 연산은 4가지
풀이
1. 완전탐색 경우를 있는그대로 그려보자
2. DP 가능 여부 판단
- 같은 함수들이 동일하게 여러번 호출된다.
- 동일한 함수에서 구하는 값들은 동일해야한다.
3. 요구 내용을 점화식으로 표현
⚠️ 식 자체를 받아들이려고 하지 말고 (my Dagari로 될리가없다)
그래프 이미지를 보면서 생각하자! !
그냥 저 그래프를 식으로 옮긴 것 뿐이다.
4. 코드로 구현
# 정수 X 입력받기
x = int(input())
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 30001
# DP 진행 (bottom-up)
for i in range(2, x+1) :
#현재의 수에서 1을 빼는 경우
d[i] = d[i-1] + 1
# 2로 나누는 연산이 가능한 경우
if i % 2 == 0 :
d[i] = min(d[i], d[i//2] + 1)
# 3으로 나누는 연산이 가능한 경우
if i % 3 == 0 :
d[i] = min(d[i], d[i//3]+1)
# 5로 나누는 연산이 가능한 경우
if i % 5 == 0 :
d[i] = min(d[i], d[i//5] + 1)
1번의 무조건 계산과 3번의 if문에서 계속
인덱스 i에 해당하는 최소의 연산횟수를 저장해둔 d[i]와 비교하면서,
인덱스 i의 새로운 최소의 연산횟수가 등장하면 갱신한다.
이런 식으로 를 수행하고 있다.
연산과정 생각하기
이렇게 계속 연산된다.
이렇게 부분연산이 다른 연산에서도 still working 함을 보장하는게 중요한 것 같다!
개미 전사
바닥 공사
효율적인 화폐 구성
Author And Source
이 문제에 관하여(ynamic Programming - 예제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@yesterdaykite/Dynamic-Programming-예제
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
효율적인 화폐 구성
Author And Source
이 문제에 관하여(ynamic Programming - 예제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@yesterdaykite/Dynamic-Programming-예제
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여(ynamic Programming - 예제), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yesterdaykite/Dynamic-Programming-예제저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)