[JAVA] 백준 1463. 1로 만들기

이 글은 읽는데 약 5분이 걸립니다.

※개인 공부 목적의 정리글입니다.
이 글의 내용이 최선의 해답은 아닐 수 있습니다.

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

  1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
  2. X가 2로 나누어 떨어지면, 2로 나눈다.
  3. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

힌트

10의 경우에 10 → 9 → 3 → 1 로 3번 만에 만들 수 있다.

풀이

힌트를 보고 단순히 큰 수부터 나누는 걸로 시작하겠다고 생각하면 안된다. 반례로 10만 보아도 큰 수부터 나누면 10->5->4->2->1로 네 번의 연산이 필요하지만 실제로는 10->9->3->1로 세 번의 연산으로도 가능하다. 이에 유의하자.

테스트 케이스를 순서대로 나열해 보아도 딱히 개수 등에서 규칙이 보이지 않는다.

Bottom-Up 방식으로 풀 것이다. 배열을 두고 작은 수부터 N까지 반복문으로 올라가면서 각 숫자의 연산횟수를 구해나가서 마지막에 N의 최소 연산 횟수를 구한다.

배열의 값은 해당 인덱스에 해당하는 숫자의 최소 연산 횟수이다. N은 1이상이므로 배열(이하 dp)의 0번 값은 무시해도 된다. dp[1]은 무얼까? 1은 이미 1이므로 연산할 필요가 없으므로 0이다.

dp[2]는? 2에 적용할 수 있는 연산은 1빼기와 2로 나누기이다. 어느쪽이든 한 번만에 1이 나오므로 연산횟수 1이 dp[2]에 저장된다. 이런식으로 숫자를 올라가면서 이전에 구한 연산횟수를 이용해서 배열을 채워나간다.

조금 더 가보자. dp[3]일때.
– 1빼기: dp[2] + 1 = 1 + 1 = 2회
– 3나누기: dp[1] + 1 = 0 + 1 = 1회

1빼기를 3에 적용하면 2가 된다. 2를 1로 만드는 최소 연산 횟수는 아까 구했으므로 그 값에다 이번에 한 번 연산했으므로 1을 더해 총 2회이다.
3나누기를 적용하면 바로 1이 된다. dp[1]=0이므로 이번에 한 연산횟수 1이 곧 답이다.

이후 나온 횟수 중 당연히 더 작은 쪽을 고르면 된다.

한번 더 예시를 들어보자. N=7이라면?

  • dp = [0, 0, 1, 1, 0, 0, 0, 0]
  • dp[4]
    • 1빼기: dp[3]+1 = 1+1 = 2
    • 2나누기: dp[2]+1 = 1+1 = 2
    • dp[4] = min(2, 2) = 2
  • dp = [0, 0, 1, 1, 2, 0, 0, 0]
  • dp[5]
    • 1빼기: dp[4]+1 = 2+1 = 3
    • dp[5] = min(3) = 3
  • dp = [0, 0, 1, 1, 2, 3, 0, 0]
  • dp[6]
    • 1빼기: dp[5]+1 = 3+1 = 4
    • 2나누기: dp[3]+1 = 1+1 = 2
    • 3나누기: dp[2]+1 = 1+1 = 2
    • dp[6] = min(4, 2, 2) = 2
  • dp = [0, 0, 1, 1, 2, 3, 2, 0]
  • dp[7]
    • 1빼기: dp[6]+1 = 2+1 = 3
    • dp[7] = min(3) = 3
  • dp = [0, 0, 1, 1, 2, 3, 2, 3]

위와 같은 순서로 결국 N=7이면 답은 dp[7]=3이다. 위 내용을 보고 흐름이 이해되었으면 한다. 다시 요약하자면, 작은 수부터 올라가며 현재 수에 적용 가능한 모든 연산을 한다. 이때 이전에 구했던 값을 참조하며, 그 값에 현재 연산횟수 1을 더한다. 그렇게 나온 모든 횟수 중 가장 작은 값을 다시 배열에 저장한다.

코드

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
sb = new StringBuilder();

int N = Integer.parseInt(br.readLine());
int dp[] = new int[N+1];
dp[0] = dp[1] = 0;

for(int i=2; i<=N; i++){
    dp[i] = dp[i-1] + 1;  // 먼저 1뺐을 때 연산횟수를 dp[i]에 저장. 이후 2또는 3으로 나눴을 때 이 값이 더 크면 교체됨

    if(i%2 == 0){
        dp[i] = Math.min(dp[i], dp[i/2]+1);
    }
    if(i%3 == 0){  // 2와 3 모두 나눠 떨어지는 경우 있어서 else if 처리는 안됨
        dp[i] = Math.min(dp[i], dp[i/3]+1);
    }
}

sb.append(dp[N]);

System.out.println(sb.toString());
br.close();

dp의 0번과 1번 값은 미리 0으로 정한다. 사실 기본 초기값이 0이라 필요없기는 하나 일부러 써놨다.

i=2부터 N까지 반복문으로 순회한다. i에서 1을 뺐을 때의 연산횟수를 계산해 일단 dp[i]에 저장한다. 1빼기 연산은 모든 경우에 가능하므로 조건문을 걸 필요가 없다. dp[i]에 저장된 값은 이후 2나 3으로 나눴을 때의 연산 횟수보다 크면 더 작은 값으로 변경될 것이다.

i가 2로 나눠 떨어지는 경우, 3으로 나눠 떨어지는 경우를 모두 체크한다. 6처럼 2와 3모두 나눠떨어지는 경우가 있어 if…else if로 묶으면 안되고 두 조건을 모두 검사해야한다.

dp[i]와 2또는 3으로 나눴을 때 연산횟수 중 더 작은 쪽으로 dp[i]의 값을 정한다.

마지막으로 dp[N]을 출력해주면 끝이다.

댓글