[ 백준 2579 ] 1로 만들기 (C++)

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

1463번: 1로 만들기

 

문제!

---

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

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

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

 

---

문제는 간단했습니다!

 

3가지 방법을 통해 N을 1로 만들어 주면 되는 문제!

 

 

바로 시작!

---

일단 저는 cal 이라는 배열에 숫자마다 이때까지의 사용횟수를 저장해 주었습니다. >> cal[1] =  N에서 1까지의 최소횟수

int cal[1000001] = {0}; // 여기는 이때까지 사용한 횟수를 저장
vector <int> memo;// 숫자저장

 

최솟값들을 선언해주고

for (int i = 0; i < N; i++) {
        cal[i] = 987654321;
    }

 

memo 벡터에 나오는 모든수들을 넣어주고 빼내면서 1이 될 때까지  반복 해주었습니다.

 memo.push_back(N);
    while (memo.size()) { // 하나씩 넣어주면서 계속 해주기
        int num = memo.back();
        memo.pop_back();

        if (num==1) {
            break;
        }

        if (num%3==0) { // 3으로 나눈값
            cal[num / 3] = min(cal[num / 3], cal[num] + 1);
            memo.push_back(num / 3);
        }
        if (num % 2 == 0) {//2 로나눈값
            cal[num / 2] = min(cal[num / 2], cal[num] + 1);
            memo.push_back(num / 2);
        }
        
        cal[num - 1] = min(cal[num - 1], cal[num] + 1);// -1
        memo.push_back(num-1);
    }

 

 

여기 까지만 해도 정답이긴 한데 제 풀이보다 더 빠른 풀이들이 있어서..... 

 

 

 

다시 시작! 

 

바로 바텀 업 방식.... 제가 했던 방식은 N에서 부터 점점 내려가는 방식이지만

이 방식은 0 부터 N을 찾아가는 방식!

 

가짓수가 줄어들지는 않지만 저처럼 모든 숫자를 저장해 나가면서 찾는것 보다는 훨씬 빠른 방법이네요!

(사용횟수가 N번을 벗어나지 않기 때문에!)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n ;
	vector<int> dp(n + 1);

	//bottom-up
	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (!(i % 3)) dp[i] = min(dp[i],dp[i / 3] + 1);
		if (!(i % 2)) dp[i] = min(dp[i], dp[i / 2] + 1);
	}

	cout << dp[n] << endl;
	return 0;
}

 

더 쉽게 풀어 나갈수 있는 문제였습니다...

 

 

 

 

ALL1

#include <iostream>
#include <vector>
using namespace std;

int cal[1000001] = {0}; // 여기는 이때까지 사용한 횟수를 저장
vector <int> memo;// 숫자저장

int main() {
    int N;
    cin >> N;
    
    for (int i = 0; i < N; i++) {
        cal[i] = 987654321;
    }
    memo.push_back(N);
    while (memo.size()) { // 하나씩 넣어주면서 계속 해주기
        int num = memo.back();
        memo.pop_back();

        if (num==1) {
            break;
        }
        if (num%3==0) { // 3으로 나눈값
            cal[num / 3] = min(cal[num / 3], cal[num] + 1);
            memo.push_back(num / 3);
        }
        if (num % 2 == 0) {//2 로나눈값
            cal[num / 2] = min(cal[num / 2], cal[num] + 1);
            memo.push_back(num / 2);
        }
        cal[num - 1] = min(cal[num - 1], cal[num] + 1);// -1
        memo.push_back(num-1);
    }
    cout << cal[1] << endl;

}

 

 

ALL2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	int n;
	cin >> n ;
	vector<int> dp(n + 1);

	//bottom-up
	dp[1] = 0;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		if (!(i % 3)) dp[i] = min(dp[i],dp[i / 3] + 1);
		if (!(i % 2)) dp[i] = min(dp[i], dp[i / 2] + 1);
	}

	cout << dp[n] << endl;
	return 0;
}

 

 

 

 

 

 

틀린점이 있다면 댓 달아주세요!