백준 : 1463번, 1로 만들기

문제 주소 : www.acmicpc.net/problem/1463

정답 비율 : 32.217% (2020.12.17 11:59 기준)

1463번: 1로 만들기

 

 

문제 요약 : 정수 n에 대하여 다음 3가지의 연산을 할 수 있습니다.

1. 3의 배수이면 3으로 나눌 수 있습니다.

2. 2의 배수이면 2로 나눌 수 있습니다.

3. 그냥 1을 뺀다.

 

-> 어떤 수가 주어질 때 위 3가지의 연산의 사용 횟수를 최소로 하여 1로 만드면 됩니다.

-> n의 범위는 다음과 같습니다. 1 <= n <= 1000000

 

문제 풀이

DP이라는 느낌을 받으면 간단한 DP문제입니다. 

점화식은 다음과 같습니다.

 

0. dp[0] = -1, n >= 1 일 때 다음이 성립합니다.

1. dp[n] = 1 + dp[n - 1] (조건 X)

2. dp[n] = 1 + dp[n / 2] (조건 : 2의 배수)

3. dp[n] = 1 + dp[n / 3] (조건 : 3의 배수)

 

여기서 여러 개의 식을 만족할 때에는 그중 최소 값을 저장합니다.

 

코드는 다음과 같습니다.

 

C99

#include<stdio.h>

int arr[1000001];

int main(void)
{
    int n, i = -1;
    
    scanf("%d", &n);
    
    arr[0] = -1
    
    for(i = 1; i <= n; i++)
    {
    	arr[i] = 1 + arr[i - 1];
    	
    	if(i % 2 == 0 && arr[i] > 1 + arr[i / 2])
    		arr[i] = arr[i / 2] + 1;
    		
    	if(i % 3 == 0 && arr[i] > 1 + arr[i / 3])
    		arr[i] = arr[i / 3] + 1;
	}
    
    printf("%d\n",arr[n]);
    
    return 0;
}

 

Python3

#solve 1463    

n = int(input())

dp = [-1]

for i in range(1, n + 1) :
    if i % 6 == 0 :
        dp.append(min(1 + dp[i - 1], 1 + dp[int(i / 2)], 1 + dp[int(i / 3)]))
    elif i % 3 == 0 :
        dp.append(min(1 + dp[i - 1], 1 + dp[int(i / 3)]))
    elif i % 2 == 0 :
        dp.append(min(1 + dp[i - 1], 1 + dp[int(i / 2)]))
    else :
        dp.append(1 + dp[i - 1])
        
print(dp[n])

 

-> 처음 문제를 접했을 때 BFS로 모든 경우의 수를 조사해야 하나 하고 코드를 짜는 중에 DP문제임을 깨달았습니다.