백준 1463번: 1로 만들기

1로 만들기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	48311	15693	10231	32.331%

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

예제 입력 1 

2

예제 출력 1 

1

예제 입력 2 

10

예제 출력 2 

3

힌트

10의 경우에 10 -> 9 -> 3 -> 1 로 3번 만에 만들 수 있다.

출처

• 문제를 번역한 사람: baekjoon
• 문제의 오타를 찾은 사람: cyj101366 jugol
• 데이터를 추가한 사람: dynamiseus

알고리즘 분류

• 다이나믹 프로그래밍

DP (다이나믹 프로그래밍)으로 푸는 문제이길래 생각했던 과정들을 간단히 정리해본다.

문제가 요구하는 내용은 단순하다. 10^6 보다 작은 자연수를 입력으로 받고, 그 수를 2 또는 3 으로 나누거나, 1을 빼서 1을 만들어주면 된다.

다만 최소한의 연산 횟수를 찾는 것이 목적이기 때문에 힌트에 쓰여있는 것처럼 수에 따라서 계산 순서가 달라질 수 있으므로 3으로 나눠지면 3으로 나누고, 2로 나눠지면 2로 나누고, 둘 다 아니라면 1을 빼는 식으로는 최소 연산 횟수를 찾을 수 없다.

따라서 DP를 이용하는 것이 적절하다. (알고리즘 분류에도 써 있다.)

지난번에 풀었던 계단 오르기 문제도 DP를 이용하는 것이었는데, 정수형 배열을 만들어 현재 위치로 올 수 있는 경우를 계산했듯 이 문제도 배열을 이용해야 할 느낌이 든다.

그렇다면 일단 배열을 하나 만들고 생각하자.

int operation[1000003];

충분한 크기의 배열을 만들었다. 이제 작은 수부터 하나하나씩 접근해보자.

배열의 인덱스에는 입력받은 수가 들어간다고 하면 operation[1] 에는 0이 들어가야 한다.

다음 인덱스인 operation[2] 에는 1이 들어가야 한다. (2 -> 1)

같은 원리로 operation[3] 에는 1이 (3 -> 1), operation[4] 에는 2가 들어가야 한다. (4 -> 2 -> 1)

위 과정들을 정리해보면

1. 3의 배수보다 1이 크고 2로 나누어 떨어지는 경우 -> 1을 빼거나 2로 나눈다. (작은 값 찾기)

2. 3의 배수보다 1이 큰 경우 -> 1을 뺀다.

3. 3으로 나누어 떨어지고 2로도 나누어 떨어지는 경우 -> 3으로 나누거나 2로 나눈다. (작은 값 찾기)

4. 3으로 나누어 떨어지는 경우 -> 3으로 나눈다.

5. 2로 나누어 떨어지는 경우 -> 2로 나눈다.

6. 만족하는 조건이 없는 경우 -> 1을 뺀다.

이 정도면 반례는 다 잡은듯하다. 코드로 짜보자.

#include <stdio.h>
 
int main(void) {
    int N;
    int operation[1000003];
    scanf("%d", &N);
    
    operation[1] = 0;
    
    for(int i = 2; i<=N; i++) {
        
        if(i%3 == 1 && i%2 == 0) operation[i-1] < operation[i/2] ? operation[i] = operation[i-1] + 1 : operation[i] = operation[i/2] + 1;
        else if (i%3 == 1) operation[i] = operation[i-1] + 1;
        else if (i%6 == 0) operation[i/3] < operation[i/2] ? operation[i] = operation[i/3] + 1 : operation[i] = operation[i/2] + 1;
        else if (i%3 == 0) operation[i-1] < operation[i/3] ? operation[i] = operation[i-1] + 1 : operation[i] = operation[i/3] + 1;
        else if (i%2 == 0) operation[i-1] < operation[i/2] ? operation[i] = operation[i-1] + 1 : operation[i] = operation[i/2] + 1;
        else operation[i] = operation[i-1] + 1;
        
        //printf("operation[%d]: %d\n", i, operation[i]);
        
    }
    
    printf("%d", operation[N]);
}

(중간에 로그는 무시합니다.)

그럼 정답!

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출한 시간
9632573	kyr9389	1463	맞았습니다!!	4904 KB	8 ms	C++ / 수정	867 B	47분 전