1463 - c++

요약

1. 3으로 나누어 떨어지면 3으로 나누거나

2. 2로 나누어 떨어지면 2로 나누거나

3. 1을 빼거나 해서

4. 어떻게 해야 가장 빨리, 입력받은 N을 1로 만들 수 있는가?

 

아이디어

들어가기에 앞서 나의 첫 다이나믹 프로그래밍 문제이다. 답을 보고 풀었다.

 

강의에서는 먼저 테이블을 정의한다음 점화식을 찾았다.

 

테이블 정의

이 문제의 테이블은 D[i] = i

각 숫자에 대응되는 인덱스를 테이블로 만들 수 있을 것 같다

 

점화식

d[12] = d[12/4], d[12/2], d[12-1]

d[3] = d[3/3], d[3-1]
d[6] = d[6/3], d[6/2], d[6-1]
d[11] = d[11-1]

이런식으로 점화식을 만들 수 있을 것 같다.

 

하지만 나 혼자 풀어 볼 때 무조건 재귀를 쓰겠지??라는 생각에 재귀를 사용하여 풀려다가 이게 맞나 싶어 답을 봤을 때 

그분은 for문을 사용해 풀고 계셨다.

 

그분의 풀이를 보기에 앞서 나의 풀이 먼저 보고 가자(보기 싫겠지만)

 

나의 풀이

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

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

int dp(int num){
  if(num == 1)return 0;
  if(d[num-1] == 0) dp(num-1);
  if(num%2 == 0 && d[num/2] == 0) dp(num/2);
  if(num%3 == 0 && d[num/3] == 0) dp(num/3);

}

int main(){
  init();
  cin >> n;
  d[1] = 0;
  dp(n);
  cout << d[n];
  return 0;
}

미완성 코드이다 이 이상으로 어떻게 해야 할지 모르겠어서 멈췄다. 대체 저 다음 뭐가 가장 작은 값인지 판단하고 어떻게 배열에 저장해야 할지 감이 안잡 혔다. 그런데 답을 보고 

와.... 굳이 위에서 아래로 안 내려 가도 아래에서 위로 올라갈 수도 있겠구나 싶었다.

 

그분의 풀이

#include <bits/stdc++.h>

using namespace std;
void init(){
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}

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

int main(){
  init();
  cin >> n;
  d[1] = 0;
  for(int i = 2; i <= n; ++i){
    d[i] = d[i-1]+1;
    if(i%2==0)d[i] = min(d[i], d[i/2]+1);
    if(i%3==0)d[i] = min(d[i], d[i/3]+1);
  }
  cout << d[n];
  return 0;
}

차근 차근 분석해 보자

왜 이분은 

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

를 가장 앞에 붙였을 까?

감히 생각해 보자면 항상 가능하기 때문이지 않을까 싶다. 즉 불가능할 때가 없기 때문에 앞에 놓은 것이라 생각한다.

항상 가능한 것이 먼저 나와야 그다음 될 수도 있고 안 될 수도 있는 조건에서 최솟값을 비교할 수 있기 때문이다.

 

문제를 풀며

첫 다이내믹 프로그래밍 문제인 만큼 나에겐 정말 어려웠다.

오늘 얻어 간 게 있다면 굳이 재귀를 쓰지 않아도 for 문으로 풀이가 가능하고 위에서부터가 아니라 아래서부터 차근차근 풀어 갈 수 있구나라는 것을 알았다.

처음 시뮬레이션 문제를 풀었을 때가 생각난다. 그때는 내가 진짜 이걸 할 수 있을까? 싶었는데 몇 가지 유형들의 문제를 풀어보고 비슷한 유형의 문제는 바로 풀 수 있었던 나 자신을 생각하며 다이내믹 프로그래밍도 열심히 연습 하자 화이트에 엥