문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력 & 출력
- 입력 : 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
- 출력 : 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.
풀이
: 풀이는 다음 블로그를 참고하였습니다. https://bio-info.tistory.com/159
import sys
n = int(sys.stdin.readline())
d= [0] * (n+1) # 값을 저장하는 배열 생성
for i in range(2, n+1):
d[i] = d[i-1] + 1
if i%2 == 0:
d[i] = min(d[i], d[i//2] + 1)
if i%3 == 0:
d[i] = min(d[i], d[i//3] + 1)
# 결과 출력
print(d[n])코드 이해
-
d= [0] * (n+1) : N보다 작거나 같은 값들에 대해서 1로 만드는데 최소인 값을 저장하는 배열을 생성한다. 각 자리의 값은 1씩 차이나기 때문에 기존 값에서 1을 빼는 연산과 동일하게 취급 가능하다.
-
for i in range(2, n+1) : 반복문을 사용해서 2부터 N값까지 반복한다. 2부터 시작하는 이유는 0의 경우 위의 연산으로 값을 만들 수 없으며, 1의 경우 이미 달성하였기에 계산에 불필요 하기 때문이다.
-
d[i] = d[i-1] + 1 : 각 자리의 연산은 앞 자리의 연산 수에 1을 더한 값으로 만들 수 있다. 이 과정은 1을 더하는 연산과 동일하다.
-
d[i] = min(d[i], d[i//(2 or 3)] + 1) : 앞의 2나 3으로 나눈 자리의 값에 +1을 해주는 것은 2나 3으로 나눈 연산을 한번 수행했다는 의미이다. 따라서 1을 빼는 연산과 해당 연산의 수행 횟수를 비교해 최소값을 선택하게 된다.
느낀점.
: DP에 감을 못잡다가 어느정도 아이디어를 잡아가는 것 같다. 고민하다 풀이를 참고하였으나, 이러한 방식으로 접근하는구나 생각하게된 경험이였다.
참고
[백준] 1463 1로 만들기 (DP) - Python / 자세한 설명 / 여러가지 풀이 / 실버1
: https://bio-info.tistory.com/159
