[BOJ] 1로 만들기 (no.1463)
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
출력
첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
🤔 생각
-
dp 문제는 처음에 케이스를 잘 나누는게 중요하다.
-
점화식 구상할 땐 top-down 방식으로 생각하는게 더 수월한것 같다.
-
3으로 나누어지면 반드시 3으로 나누란 얘기가 아니고, 세가지 경우를 모두 적용할 수 있다는 말이다. 처음에 전자로 이해해버려서 삽질했다... (바본가)
케이스
- 3으로 나누어 떨어지는 경우
- 2로 나누어 떨어지는 경우
- 그 외
배열 정의
dp[i] : 정수 i일 때 최소 연산 횟수
🔥 점화식
dp[i] = min(dp[i//3]+1, dp[i//2]+1, dp[i-1]+1)
논리가 대략 이렇다는거고 그대로 쓰면 안된다.
2나 3으로 나누어지는지 확인도 해야하므로 조건문으로 추가 처리 해주면 된다.
📌 내 풀이
import sys
input = sys.stdin.readline
n = int(input())
dp = [0]*(n+1)
for i in range(2,n+1):
dp[i] = dp[i-1] + 1
if i%3 == 0 and dp[i] > dp[i//3]+1: dp[i] = dp[i//3]+1
if i%2 == 0 and dp[i] > dp[i//2]+1: dp[i] = dp[i//2]+1
print(dp[n])
✔ 회고
- 짜고 나면 허무할 정도로 쉽지만 아직 점화식 구상이 서툴다.
- 어려워도 결국엔 고이게 될거다! DP 쭉쭉 밀자
Author And Source
이 문제에 관하여([BOJ] 1로 만들기 (no.1463)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@wisepine/BOJ-1로-만들기-no.1463저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)