문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
X가 3으로 나누어 떨어지면, 3으로 나눈다.
X가 2로 나누어 떨어지면, 2로 나눈다.
1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 10^6보다 작거나 같은 정수 N이 주어진다.
접근 방법
DFS방식의 재귀함수로 모든 수를 탐색하면서 1이 되는 최소 횟수를 찾을 수도 있지만, DP 문제이므로 이전 결과를 저장하면서 1에 도달하는 최소횟수를 갱신하는 방식으로 풀어야 할 것 같다.
문제 주어진 반대로 1부터 시작하여 정수 X까지 도달할 때의 최소 횟수를 저장하는 방식으로 접근하였다.
파이썬 풀이
n=int(input())
# 1부터 시작해서 n이 되는 상황 찾기
# n 은 1보다 같거나 커서 10^6, 즉 백만 까지 이므로 count 배열을 만들어도 시간초과 걱정은 없음
def dp(n):
i=1 # X까지 도달할 정수 i 선언 및 할당
arr = [0]*(n+1) # 각 정수까지의 횟수를 저장하는 배열 선언 및 항당
while(i!=n): # X에 도달할 때까지
if not arr[i+1]: # 횟수가 0으로 미 갱신 상태면 새로 할당
arr[i+1] = arr[i]+1
else:
arr[i+1] = min(arr[i+1],arr[i]+1) # 횟수가 있으나 더 작은 횟수로 갱신
if i*3 <= n: # 인덱스 초과 방지
if not arr[i*3]:
arr[i*3] = arr[i]+1
else:
arr[i*3] = min(arr[i*3],arr[i]+1)
if i*2 <= n:
if not arr[i*2]:
arr[i*2] = arr[i]+1
else:
arr[i*2] = min(arr[i*2],arr[i]+1)
i+=1 # i를 하나씩 키우며 무지성 Brute Force의 힘을 보여주자!
return arr[n]
print(dp(n))숏코딩 분석하기
d=[-1] for i in range(1,int(input())+1):d+=[min(d[i//3]+i%3,d[i//2]+i%2,d[i-1])+1] print(d[-1])
i를 1부터 n까지 1씩 증가시키면서d라는 배열(배열의 인덱스 = 숫자, 원소 = 숫자에 도달하는 최소 횟수)를 만들어 크기를 늘리는 방식으로 접근하였다.
min함수 인수들의 의미를 생각해보면
d[i//3]+i%3은 i가 되기 위해 3으로 나눠지는 숫자가 만들어지는 최소 횟수가 저장된d[i//3]에다가 3으로 나눠지는 숫자까지 3으로 나눈 나머지 만큼 1을 빼는 횟수(+i%3)를 추가 해야 한다.
예를 들어 설명하면,
1이 7이 경우의 수가 아래와 같고 이 중 최소 횟수를 비교하는 식이다.
1. 3으로 나누는 경우 : 1(+0) -> 2(+1) -> 6(+2) -> 7(+3)으로
2. 2로 나누는 경우 : 1(+0) -> 3(+1) -> 6(+2) -> 7(+3)
3. 1빼는 경우 : 6(+n) -> 7(+n+1)
2와 3으로 나눠지는 6이 되기 까지의 횟수 min(+2, +2, +n) 중의 최소 회수 + 1이 7이 되는 최소 횟수가 된다.
C++ 풀이
#include <iostream>
#include<algorithm>
using namespace std;
int main() {
int i,n;
cin >> n;
int arr[n+1] = {-1};
for(i=1;i<=n;i++){
arr[i] = min({arr[i/3]+i%3,arr[i/2]+i%2,arr[i-1]})+1;
}
cout << arr[n];
}