iframe-proxy | Sunbelt Computer Software

History

72 lines (68 loc) · 1.75 KB

Raw

#include <iostream>

int d[1000001];

using namespace std;

// 1로 만들기

// N을 1로 만드는 **최소** 연산 횟수

// 3으로 나누는 것이 빠르므로, 2보다 3을 먼저 나눈다. -- 그리디 알고리즘. 예외.

// ** 점화식의 정의를 세워보자 **

// D[N] : N을 작게 만들 수 있는 방법

// 큰문제 단계와 나머지 다시 전체 문제로 나누면 좋다.

// N -> N/3 (1번) 과 N/3 -> 1 (D[N/3])

// N -> N/2 (1번) 과 N/2 -> 1 (D[N/2])

// N -> N-1 (1번) 과 N-1 -> 1 (D[N-1])

// D[N] = min(D[N/3], D[N/2], D[N-1])

// D[1] = 0 // 1->1

//--------- TOP DOWN ----------//

// n에서부터 내려가면서.. 재귀호출

int go(int n)

{

if (n == 1)

return 0;

if (d[n] > 0)

return d[n]; // memoization 기억하고 있는 건 그대로 사용

// D[n-1] : **아무때나** 가능함으로, 아무때나 를 먼저 해서, **비교의 기준**으로 만들어준다.

d[n] = go(n - 1) + 1;

// D[n/2]

if (n % 2 == 0)

{

int temp = go(n / 2) + 1;

if (d[n] > temp)

d[n] = temp;

}

// D[n/3]

if (n % 3 == 0)

{

int temp = go(n / 3) + 1;

if (d[n] > temp)

d[n] = temp;

}

return d[n];

}

int main()

{

int n;

cin >> n;

// cout << go(n) << '\n';

//--------- BOTTOM UP ----------//

d[1] = 0;

for (int i = 2; i <= n; i++)

{

d[i] = d[i - 1] + 1;

if (i % 2 == 0 && d[i] > d[i / 2] + 1)

{

d[i] = d[i / 2] + 1;

}

if (i % 3 == 0 && d[i] > d[i / 3] + 1)

{

d[i] = d[i / 3] + 1;

}

cout << d[n] << '\n';

return 0;

}

// 시간 복잡도

// 함수의 호출 횟수 * 함수의 시간 복잡도

// - 문제의 개수 - -문제 1개 푸는데 필요한 시간-

// 점화식: D[N] = min(D[N/3], D[N/2], D[N-1])

// N * O(1)

// 따라서 시간 복잡도: O(n)

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

dynamic1463.cpp

Latest commit

History

dynamic1463.cpp

File metadata and controls