[백준] 1463번 1로 만들기

문제: 1463번: 1로 만들기

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x10.md at master · encrypted-def/basic-algo-lecture

 

• 내 풀이

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <limits>
#include <bits/stdc++.h>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	vector<int> table(n+1); // 0번 인덱스는 안 써~

	// 1 은 연산 횟수가 0 이니까 그냥 2부터 시작하기
	for (int i = 2; i < n + 1; i++) {
		int threeNum = INT_MAX;
		int twoNum = INT_MAX;
		int oneNum = INT_MAX;

		if (i % 3 == 0) {
			threeNum = table[i / 3] + 1;
		}
		if (i % 2 == 0) {
			twoNum = table[i / 2] + 1;
		}
		oneNum = table[i - 1] + 1;

		table[i] = min({ threeNum, twoNum, oneNum }); // 최솟값 넣어주깅~
	}
	cout << table[n]; // 최솟값 출력

	return 0;
}

 

• 강의 풀이

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/161694ef04f04d8dbe826e253622c1cb
#include <bits/stdc++.h>
using namespace std;

int d[1000005];
int n;

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  d[1] = 0;
  for(int i = 2; i <= n; i++){
    d[i] = d[i-1]+1;
    if(i%2 == 0) d[i] = min(d[i],d[i/2]+1);
    if(i%3 == 0) d[i] = min(d[i],d[i/3]+1);
  }
  cout << d[n];
}

 

음. 내 풀이보다 강의 풀이가 훨씬 깔끔했다.

 

문제 풀이 핵심은 그냥 이전값을 이용하는 점화식을 잘 생각해내는 것? 흠.. 근데 나는 dp 풀 때마다 그게 아직 잘 안된다.. 계속 하다보면 감이 잡히겠지??