[백준] 1463 1로 만들기

이 문제는 DP 문제 풀이를 시작하고나서 가장 처음에 접한 문제입니다.

 

어려운 문제는 아니지만, 처음 DP문제를 접한 사람들에게는 생소한 부분 일 수 있습니다.

 

• 문제 접근 방식
  bottom-up 방식으로 접근한다면 쉽게 풀 수 있습니다.
  2부터~입력값 까지 도달하는 횟수의 최소값을 비교하여 각각 배열에 넣어줍니다.
  arr[1]=0
  arr[2]=1 <- 2-1
  arr[3]=1 <- 3/3
  arr[4]=2 <- (4-1)/3
  ....
  그렇다면 어떻게 각각의 입력값까지 도달하는 횟수가 최소값인지 비교할 수 있을까요?
  arr[10]을 예로 들어 보겠습니다.
  위에 예시를 이어서,
  arr[5]를 만드는 방법은 arr[4]까지의 방식이 최소값이기 때문에 arr[5]=arr[5-1]+1=3 가 됩니다.
  (+1를 해준이유는 -1이라는 연산과정을 한 번 더 거쳤기 때문입니다)
  arr[6]를 만드는 방법은 arr[6]=arr[6-1]+1 = 4 , arr[6]=arr[6/2]+1 = 2, arr[6]=arr[6/3]+1 = 2 방법이 있을 수 있습니다. 이 중에서 최소값은 2 이므로 arr[6]=2가 됩니다.
  arr[7]를 만드는 방법은 arr[7]=arr[7-1]+1 = 3 이 됩니다.
  arr[8]를 만드는 방법은 arr[8]=arr[8-1]+1 = 4 , arr[8]=arr[8/2]+1 = 3 이므로 3이 됩니다.
  arr[9]를 만드는 방법은 arr[9]=arr[9-1]+1 = 4 , arr[9]=arr[9/3]+1 = 2 이므로 2가 됩니다.
  arr[10]를 만드는 방법은 arr[10]=arr[10-1]+1 = 3, arr[10]=arr[10/2]+1 = 4 이므로 3이 됩니다.
  즉 arr[i]=arr[i-1]+1 와 arr[i]=arr[i/2]+1 와 arr[i]=arr[i/3]+1 세 가지 방법중 최소값을 찾는 과정입니다. 

• 문제 적용
  for(int i=2; i<=n; i++){
     arr[i]=arr[i-1]+1;
     if(i%2==0){
        arr[i]=min(arr[i/2]+1,arr[i]); // arr[i]값은 현재 arr[i-1]+1 값이므로 arr[i/2]+1 값과 최소값을 비교해 줍니다.
     }
     if(i%3==0){
        arr[i]=min(arr[i/3]+1,arr[i]); // also if 로 하지 않는 이유는 2와3의 공배수 일 경우, arr[i/2]+1 과 arr[i/3]+1 의                                             // 비교가 필요하기 때문입니다.
     }
  }

• 전체 코드