LV2.숫자 변환하기

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

---

첫번째 접근 방법 : bfs(재귀)로 접근

문제에서 원하는건 [ 최소 연산 횟수를 return ]이기 때문에 bfs로 접근하였고, bfs를 사용하기에 queue 자료구조를 사용하였다, 인자값이 작아서 경우의수가 적을경우에는 원하는 값이 나왓지만 인자값이 엄청 큰 경우 재귀함수 반복횟수 초과 및 시간 복잡도 문제가 발생했다.

 

재귀함수 장/단점 간단 정리

[재귀함수 장점] -> 가독성 Up

1.변수의 사용을 줄일 수 있다.

2.알고리즘 자체가 재귀함수에 어울리는 경우 ex)Tree 

[재귀함수 단점] -> 시간증가 , 스택오버플로우 발생 

1.함수를 호출이 반복적으로 일어나기에 시간이 반복문보다 더 걸릴 수 있다.

2.함수 호출시마다 스택영역에 메모리가 쌓여서 결국 스택 오버 플로우 발생이 된다.

 

두번째 접근 방법 : DP로 접근하기

인자값이 크면 클수록 경우의수가 너무 많아져서 DP를 사용

x에 3가지 방법의 계산 후 계산값을 저장할 배열이 필요하므로 [ y +1 ] 만큼 배열을 만든뒤 -1로 채운다.

-1로 채운 이유는 해당 index에 접근 안했다는 표시와 y값을 못구하는경우 -1을 return하기 위해서다.

각각의 방법으로 구한 계산 값을 index로 취급하고 , 배열[index]에 계산한 횟수를 저장한다.

 

ex) x=10 , y=40 ,n=5 인경우

dp[10]	dp[11]	dp[12]	dp[13]	dp[14]	dp[15]	...	dp[20]	...	dp[30]
0(Start)	-1	-1	-1	-1	1(10+5)		1(10*2)		1(10*3)

이런식으로 dp에 저장한다. 그리고 연산 중에 겹치는 값이 있을텐데  최소의 연산 횟수를 구하는것이기에

저장하려는 계산값과 저장되있는 계산값중 최소인것을 선택하여 저장하게하면된다.(최소 연산 횟수가 아닌경우 할필요가 없어짐)

 

이렇게 배열의 길이만큼 순회하면 원하는 값을 도출 할 수 있다.

 

코드영역

#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include<cmath>
using namespace std;

int solution(int x, int y, int n) 
{
    int answer = 0;

    vector<int> dp;
    for (int i = 0; i < y + 1; i++) { dp.push_back(-1); }//dp 배열 data값을 전부 -1 초기화

    dp[x] = 0; // 초기 시작값 설정
   
    for (int i = x; i < y + 1; i++)
    {
        //해당 dp[i]에는 접근하지 않았기에 넘어감
        if (dp[i] == -1) continue;

        if (i * 2 <= y)
        {
            //계산한 값이 -1이면 접근하지 않았기에 바로 dp에 계산값을 초기화
            if (dp[i * 2] == -1) { dp[i * 2] = dp[i] + 1; }//해당 dp자리에 연산 횟수data가 있는경우 최소값을 골라서 초기화
            else { dp[i * 2] = min(dp[i] + 1, dp[i * 2]); }
        }

        if (i * 3 <= y)
        {
            if (dp[i * 3] == -1) { dp[i * 3] = dp[i] + 1; }
            else { dp[i * 3] = min(dp[i] + 1, dp[i * 3]); }
        }

        if (i + n <= y)
        {
            if (dp[i + n] == -1) { dp[i + n] = dp[i] + 1; }
            else { dp[i + n] = min(dp[i] + 1, dp[i + n]); }

        }
    }
    //dp배열 길이만큼 순회 후 dp[y]에 도달한 연산 횟수 값을 반환 
    return dp[y];
}