99클럽 코테 스터디 16일차 TIL + DP 리팩토링

백준

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

1463번: 1로 만들기

 

---

- 오늘의 학습 키워드 : DP 리팩토링

- 공부한 내용 본인의 언어로 정리하기

DP

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());
    int[] count = new int[N];

    for (int i=1; i<count.length; i++) {
      // 1을 빼는 경우
      count[i] = count[i-1] + 1;
      // 2로 나누어 떨어지는 경우
      if (i % 2 == 0) {
        count[i] = Math.min(count[i], (i / 2) + 1);
      }
      // 3으로 나누어 떨어지는 경우
      if (i % 3 == 0) {
        count[i] = Math.min(count[i], (i / 3) + 1);
      }
    }
    System.out.println(count[N-1]);
  }
}

리팩토링 (시간 초과 해결)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
  static Integer[] dp;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    dp = new Integer[N + 1];
    System.out.println(func(N, 0));
  }

  private static int func(int N, int count) {
    if (N < 2) return count;
    return Math.min( func(N/2, count+1+(N%2)), func(N/3, count+1+(N%3)) );
  }
}

- 오늘의 회고 : DP를 사용하면서 값을 저장하지 않고 따로 count를 매개변수로 받아서 효율성을 높였다.

---

99클럽 1기를 수강하면서 작성한 글입니다.

https://99club.oopy.io/

99클럽-1기 모집 중