[백준] 1463번: 1로 만들기(JAVA)

https://www.acmicpc.net/problem/11726

| keyword: 동적 계획법, 반례에 휘둘리지 말기

‼️이 문제의 정답 코드는 맨 마지막(Github Gist)에 있습니다. 중간중간의 코드들은 제 생각을 담은 일대기를 작성하였습니다.
백준 시리즈 글은 필자가 생각보다 많은 시간이 걸린 문제들의 생각을 정리해보고자 작성되었습니다.
문제의 링크는 여기를 이용해주세요!

첫번째 생각

이 문제를 딱 보고 음... 쉽겠군 하였다. 하지만 이 문제를 작성하게 된 이유이자, 시간이 많이 걸린 이유인 10의 사례를 보고 그 때부터 이 사례에 집착(?)하게 되었던 것 같다.
10은 10 -> 5 -> 4 -> 2 -> 1의 예시로 4번 들어오는데, 10 -> 9 -> 3 -> 1 의 경우로 3번 만에 답을 구할 수 있게 된다.
이 때 문제의 본질을 생각하고 벗어났어야 했는데 이와 같은 반례를 풀려고 너무 집착한게 이 문제를 오래걸린 이유가 아닐까 싶다. 반례에 집중하지 않고 문제의 본질을 깨달아야 된다는 교훈을 전해준 소중한 문제 이다.

그래서, 반례에 집중하게 되다 보니 3개의 조건을 모두 가지는 조건에 관해 생각하게 되었다. 되게 쓸데없이 밑 그림과 같이 트리 구조를 그리며 집착하였다. (시간을 엄청 들여 고민하며 )그리다가 반례가 너무 많아서 본질을 깨달아야겠다고 판단후에, 다시 문제로 들어갔다.

두번째 생각

동적 계획법의 풀이 방법인 Top-Down, Bottom-Up 방법을 각각 다시 생각해보았다.
횟수가 중요한 문제이다 보니, 각 단계에서 진행되는 프로세스에 집중해야겠다고 생각하여, 하나의 step에 집중하였다. 각 step 마다 나누기 3 / 나누기 2 / 빼기 1이 되는 걸 보면서 bottom-up 을 이용해 1부터 차근차근 찾아가며 풀어가는 방식이 적합하리라 생각하였고 다음과 같이 코드를 작성하였다.

import java.util.*;
import java.io.*;

public class Main {

   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       int num = Integer.parseInt(br.readLine());

       int[] res = new int[num+1];
       res[1]=0;
       for(int l=2;l<res.length;l++) {
           res = make_one(l, res);
       }
       System.out.println(res[res.length-1]);
   }

   public static int[] make_one(int l, int[] res) {
       if(l%3==0) {
           res[l] = 1+ res[l/3];
       }else if((l-1)%3==0) {
           res[l]= 1+res[l-1];
       }else if(l%2 ==0) {
           res[l] = 1+ res[l/2];
       }else {
           res[l]= 1+res[l-1];
       }
       return res;
   } 
}

하지만 반례에 생각하다보니 3나누기가 2나누기보다 강력하다는 함정에 허우적대서 80% 풀고 계속 고민하였다. 그리고 각 버전마다의 최솟값이 있음을 그제서야 파악하고 겨우 풀 수 있었다.

최종 코드

 

 

문제를 풀면서 반례에 목매지 않고 본질에 집중할 수 있도록 노력해야겠다고 생각했다.

 

+ 추가적인 생각

동적 계획법에서 작은 문제로 나눌 때 명확한 기준을 가지고 적용해야겠다는 생각을 했다. 백준의 11726번 2xn타일링 문제를 보면, d[n-1]+d[n-2]의 경우를 딱 보면 이해가 되는 사람이 많이 없을 것이다. 경우는 이렇게 나눠야 한다.

• 오른쪽 맨 끝에 가로로 배치되어있는 상황: d[n-1]
• 오른쪽 맨 끝에 세로로 2개가 배치되어있는 상황: d[n-2] 

이렇게 해석된다. 즉, 동적 계획법에서는 일정한 기준을 가지고 적용이 되어야 한다.