BOJ 1463: 1로 만들기

✔ 문제 링크

---

BOJ 1463: 1로 만들기

---

✔ 문제해결전략

• Dynamic Programming(DP)
• BFS

---

✔ Code 1) DP

#include <bits/stdc++.h>
using namespace std;

int arr[1000001];



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

---

✔ Code 2) BFS - 나중에 추가 예정

// coming soon

---

✔ Comment

• 테이블 정의: arr[i] = i를 1로 만드는데 필요한 최소 연산 수
• 점화식:
  arr[i] = min(arr[i-1], arr[i/3], arr[i/2]) + 1 (2, 3의 배수인 경우에만)
• 테이블 하나 잡고 1부터 차례대로 채워나가면 된다

---

✔ Check Point

정신줄 놓고 for문 안에 i다 n으로 넣어서 계속 왜 틀렸지 하면서 헤맸다. 정신차려