BAEKJOON 1463번: 1로 만들기

[2018-08-29 수요일]

* 내용: 1로 만들기

1. 문제

2. 해결 방법

 

1. 문제

---

 

* 내용

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

 

 

2. 해결 방법

---

 

* 로직

- Bottom-up 방식

- 1~10까지 차례로 값 확인

- 1을 빼는 건 무조건 실행 가능하므로 가장 먼저 실행 → 2, 3으로 나누는 것 실행 전까지는 최솟값

- 2, 3으로 나눌 시 → 나누고 난 이후의 값의 최솟값과 합산

 

* 로직 예시(예시 값: 10)

- 1을 뺄 시 → 연산 횟수 = 3

연산 횟수	연산식	값
0	-	10
1	10 - 1	9
1 + 2(arr[9]) = 3	-	1

 

- 2로 나눌 시 → 연산 횟수 = 4

연산 횟수	연산식	값
0	-	10
1	10 / 2	5
1 + 3(arr[5]) = 4	-	1

 

* 이슈

- 배열 동적 할당 시 사이즈 설정 미스

- 해결 방법: 소스 수정

변경 전	변경 후
int* arr = new int[n];	int* arr = new int[n + 1];

 

* 소스 코드

#include <iostream>
#include <string>
#include <vector>
#include <regex>
#include <stack>
#include <list>
#include <cmath>
 
using namespace std;
 
int main() {
 
    int n;
 
    cin >> n;
    
    if (n < 1 || n > 1000000) {
        return 0;
    }
    
    int* arr = new int[n + 1];
 
    arr[1] = 0;
 
    for (int i = 2; i <= n; i++) {
        if (i - 1 > 0) {
            arr[i] = 1 + arr[i - 1];
        }
        
        if (i % 2 == 0) {
            int temp = 1 + arr[i / 2];
            arr[i] = min(arr[i], temp);
        }
 
        if (i % 3 == 0) {
            int temp = 1 + arr[i / 3];
            arr[i] = min(arr[i], temp);
        }
    }
 
    cout << arr[n];
 
    return 0;
}