[220831] 백준풀기 (1463)

 

- 1463: 1로 만들기 (성공, 다시 풀어보기)

 

     첫번째 시도: X가 3으로 나누어 떨어질 때, X가 2로 나누어 떨어질 때, 그 외 경우는 1을 빼도록 나눔

      => 9, 27과 같이 계산을 적게 할 수 있는 경우를 고려하지 못함

 

     두번째 시도: (X-1)%3 == 0형태를 사용해 작은 숫자가 3이나 2로 나누어 떨어진다면 이도 고려하도록 했다.

                          또 X-1 어떤 수의 제곱수라면 그 수로 만들어주는 것이 가장 빠르게 계산하는 방법이라 생각해

                          해당 수가 제곱수인지 판별하는 함수도 만들었다.

      => 이 코드도 가장 적게 계산할 수 있는 경우를 고려하지 못했다.

 

 

     이 문제를 해결하기 위해서는 DP(다이나믹 프로그래밍)을 사용해야 했다.

     모든 각각의 숫자가 계산되는 횟수를 다 구해 저장해둔 후 그 중 최솟값을 찾아 출력하는 방식을 사용한 것이다.

     여기서 시간복잡도를 줄이기 위해 vector와 min함수 등이 필요했다.

     <dp[2] 라면 2라는 숫자에서 1이 될때까지 필요한 계산 횟수가 저장된 공간을 의미>

     < 2와 3이 기준이기 때문에 X에서 1만 빼줘도 2 또는 3으로 나누어 떨어지는 수에 접근할 수 있게된다.>

 

     1. n+1 크기의 dp 벡터를 선언한다.

        dp[1]엔 0을 넣어주고, dp[2], dp[3] 엔 1, dp[4] 엔 2를 넣어준다. 

        (위처럼 숫자가 작은 경우는 미리 계산해 넣어주었다.)

        이후 for문으로 5부터 n까지 반복하며 dp벡터에 계산값을 저장한다.

 

     2. if문을 사용해 4가지 종류로 경우의 수를 나눈다. 

         - X가 2와 3 어떤 수로도 나누어 떨어지지 않는경우

            => X에서 1을 빼주는 계산만 해주면 dp[i-1]번 계산하면 되므로 dp[i]에 dp[i-1]+1을 저장한다.

         - X가 2로 나누어 떨어지는 경우

            => dp[i/2] + 1 ~ dp[i-1] + 1 까지의 수 중 min함수를 통해 최소값을 구해 dp[i]에 저장한다.

         - X가 3으로 나누어 떨어지는 경우

            => dp[i/3] + 1 ~ dp[i-1] + 1 까지의 수 중 min함수를 통해 최소값을 구해 dp[i]에 저장한다.

         - X가 2와 3 모두로 나누어 떨어지는경우

            => dp[i/2] + 1 ~ dp[i/3] + 1 까지의 수 중 min함수를 통해 최소값을 구해 dp[i]에 저장한다.

      (여기서 +1을 해주는 이유는 1만 빼주어도 2또는 3으로 나누어 떨어지게 되기 때문에 +1을 해줌으로써

        1을 빼주는 계산을 했다고 치고, dp[i-1]까지의 계산을 고려하기 위함이다.)

 

     3. for 반복문이 끝났다면 dp[n], 최종으로 계산된 횟수값을 출력한다.