BOJ 1463 1로 만들기

문제출처 : https://www.acmicpc.net/problem/1463

1. 문제요약

- 연산1. 3으로 나누어 지면 3으로 나눔

  연산2. 2로 나누어 지면 2로 나눔

  연산3. 1을 뺌

- 위 연산 3가지를 이용하여 N을 1로 만드는 최소 횟수

- 1 <= N <= 10^6

2. 접근방법

- bfs

  N에서 N/3, N/2, N-1을 1을 만날때 까지 bfs

=> N과 N이 1로 가는 모든 과정들이 2나 3으로 무조건 나누어 떨어진다고 하면,

     N -> N/3, N/2, N-1 3개의 숫자로 뻗어나감(큐에 3개씩 저장)

     방문한 숫자는 다시 방문할 필요가 없으므로 10^6 만큼 시간이 걸림

     (물론 1을 만나자마자 bfs를 그만 두면 좀 더 빠를거임)

- dp

  N이 1이 되는 최소 횟수는 N/3, N/2, N-1 중에 최솟값 + 1

  d[n] : n이 1이 되는 횟수 로 정의한다면

  d[n] = min(d[n-1], d[n/2], d[n/3]) + 1

3. 시간복잡도

- bfs나 dp 모두 최악 N

4. 회고

- d[n] + 1 을 안해줘서 한참 고민했네...

소스코드 : dp bottom up

#include<iostream>
using namespace std;

int n, d[1000001] = { 0, 0, 1, 1 };

int main(void){
	cin >> n;
	for (int i = 4; i < n + 1; i++){
		d[i] = d[i - 1];
		if (i % 2 == 0) d[i] = d[i] > d[i / 2] ? d[i / 2] : d[i];
		if (i % 3 == 0) d[i] = d[i] > d[i / 3] ? d[i / 3] : d[i];
		d[i]++;
	}
	cout << d[n] << "\n";
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]