[BOJ/백준] 1463 1로 만들기

● [문제번호 1463] 1로 만들기

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

● 풀이 과정

: 재귀로만 모든 경우 확인하는 방법으로 구현했더니 '시간 초과' 결과가 나왔다.

2로 나눈 나머지와 3으로 나눈 나머지를 비교하여 재귀하는 방법으로 시간을 단축시킬려고 했으나 이번에 답이 옳지 않게 나왔다.

결국에 구글링을 하였다.

 

: 참고 링크에 해당 문제를 Top - Down 방식과 Bottom - Up 방식으로 모두 풀이 되어 있다.

 

: 아래 코드는 Top - Down 방식으로 구현하였다. (Bottom - Up 방식은 주석처리됨)

배열을 만들고 배열의 index를 숫자로 이용하고 배열의 값을 연산횟수로 저장한다.

index가 시작(입력된 숫자)부터 끝(1)이 될 때 까지 작아지면서

1. index가 3으로 나눠 떨어지면 (3으로 나눈 index)는 (나누기 전 index)의 값 + 1

2. index가 2으로 나눠 떨어지면 (2으로 나눈 index)는 (나누기 전 index)의 값 + 1

3. (1 뺀 index)는 (빼기 전 index)의 값 + 1

이 세 가지 작업을 모두 하는 데 값을 넣을 때 기존 값과 비교하여 작은 값으로 설정한다.

 

이를 반복하여 끝나면 index가 1인 배열의 값은 최소 연산의 횟수가 저장되어 있다.

 

● 주의 할 것

: 초깃값 설정시 습관상 0으로 두면 정답이 구해지지 않는다. (Top - Down)

 

● 참고 할 것

: 다이나믹 프로그래밍 풀이 참고 (tony9402 블로그)

https://ssu-gongdoli.tistory.com/66

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

#define INF 1000000

vector<int> dp;
int N;

// 최소 연산 횟수 구하는 함수 (Top - Down)
void calculation_TD()
{
    // 출발점
    dp[N] = 0;
    
    // index가 1이 될 때 까지 진행
    for(int i = N; i > 0; i--)
    {
        // 건너 뛸 수 인 경우
        if(dp[i] == INF)
            continue;
        // 3으로 나눠지는 경우
        if(i % 3 == 0)
            dp[i / 3] = min(dp[i / 3], dp[i] + 1);
        // 2로 나눠지는 경우
        if(i % 2 == 0)
            dp[i / 2] = min(dp[i / 2], dp[i] + 1);
        // 1을 빼는 경우
        if(i >= 2)
            dp[i - 1] = min(dp[i - 1], dp[i] + 1);
    }
    
    // 최소 연산 횟수 출력
    cout << dp[1];
}

// 최소 연산 횟수 구하는 함수 (Button - Up)
void calculation_BU()
{
    // 출발점
    dp[1] = 0;
    
    // index가 구하고자하는 N까지
    for(int i = 1; i <= N; i++)
    {
        if(dp[i] == INF)
            continue;
        if(i * 3 <= N)
            dp[i * 3] = min(dp[i * 3], dp[i] + 1);
        if(i * 2 <= N)
            dp[i * 2] = min(dp[i * 2], dp[i] + 1);
        if(i + 1 <= N)
            dp[i + 1] = min(dp[i + 1], dp[i] + 1);
    }
    
    // 최소 연산 횟수 출력
    cout << dp[N];
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 입력 과 초기화
    cin >> N;
    dp.assign(N + 1, INF);
    
    // 다이나믹 프로그래밍 (Top - Down)
    calculation_TD();
    
    // 두 방식은 같은 배열을 공유하고 있으므로 각각 실행해야 합니다
    
    // 다이나믹 프로그래밍 (Bottom - Up)
    // calculation_BU();
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [400 - 다이나믹 프로그래밍 1] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1463	1로 만들기	https://pirateturtle.tistory.com/199
2	11726	2×n 타일링	https://pirateturtle.tistory.com/200
3	11727	2×n 타일링 2	https://pirateturtle.tistory.com/201
4	9095	1, 2, 3 더하기	https://pirateturtle.tistory.com/202
5	11052	카드 구매하기	https://pirateturtle.tistory.com/203
6	16194	카드 구매하기 2	https://pirateturtle.tistory.com/204
7	15990	1, 2, 3 더하기 5	https://pirateturtle.tistory.com/205
8	10844	쉬운 계단 수	https://pirateturtle.tistory.com/206
9	2193	이친수	https://pirateturtle.tistory.com/207
10	11053	가장 긴 증가하는 부분 수열	https://pirateturtle.tistory.com/208
11	14002	가장 긴 증가하는 부분 수열 4	https://pirateturtle.tistory.com/209
12	1912	연속합	https://pirateturtle.tistory.com/210
13	1699	제곱수의 합	https://pirateturtle.tistory.com/211
14	2225	합분해	https://pirateturtle.tistory.com/212