[백준] 1463.cpp : 1로 만들기

www.acmicpc.net/problem/1463

1463번: 1로 만들기

#include <iostream>

// 두 수 중 작은 값을 리턴
#define MINI(a,b) a < b ? a : b

using namespace std;

int n;
// n까지 각각 값을 구해놓을 배열
int arr[1000001] = {0, 0, 1, 1,};

int main(void)
{
  cin >> n;

  // 4번부터 시작
  for(int i = 4 ; i <= n ; i++)
  {
    // 이번의 최솟값은 1차적으로 보았을 때 직전꺼에서 1만 더해준 값이다
    arr[i] = arr[i-1] + 1; // 1을 빼던지
    // 그런데 만약 2로 나눠떨어질 경우에는 2로 나눈 인덱스의 값+1 과 비교해본다
    if(i % 2 == 0) // 2로 나누던지
    {
      arr[i] = MINI(arr[i/2] + 1, arr[i]);
    }
    // 만약 3으로 나눠떨어질 경우에도 확인해준다
    if(i % 3 == 0) // 3으로 나누던지
    {
      arr[i] = MINI(arr[i/3] + 1, arr[i]);
    }
    // 그러면 최종적으로 이번인덱스의 최솟값이 구해진다
  }

  cout << arr[n] << '\n';
}

 

[Try]

1. 시간초과가 날 거 같긴 하지만 괜히 또 배배 꼬지 말고 2와 3으로만 이루어진 수들을 완전탐색으로 돌려 보고 싶다.

     전부는 아니고 2의배수 3의배수들만 돌리려고 했는데 로직이 틀린 듯 하다

2. 배열을 만들어놓고 에라토스테네스의 체 처럼 2와 3의 배수를 걸러주면서 값을 넣어준다. 나머지 값들은 근접한 값에 + 를 해준다

     어차피 테스트케이스로 여러번구하는것도 아니고 n 값 하나 구하는건데 굳이 모든 값들을 다 구할 필요가 없어 보인다

     그리디로? 무조건 나눈다고 좋은 것이 아니다   ex) 28

     DP 배열 구해놓는거 시간초과날것같다. O(n2) 인데 최대값이 10^6 이다 ㅠㅠ 그래도 해봐야겠따. 실제로 시간초과가 난다.

3. O(n) 으로 바꿀 여지가 있는 것 같은데 틀렸습니다 가 뜬다..

4. O(n) 으로 로직 꼼꼼하게 파악하기

 

[Point]

1. 풀이가 크게 재귀호출로 구하던지, 배열을 놓고 차근차근 채워나가며 구하던지 2개로 볼 수 있다.

2. 재귀가 더 깔끔해 보인다. 그런데 잘 이해는 가지 않는다 ㅠㅠ

 

[More]

1. 재귀 호출 (11015124)