BJ1463 1로 만들기
https://www.acmicpc.net/problem/1463
DP 또는 재귀함수를 이용해 해결할 수 있다.
이 문제에서는 재귀함수를 이용했을 때 실행시간이 더 짧았지만, 여러 테스트 케이스를 출력한다면 DP를 활용할 때는 단순히 배열에 접근해 값만 가져오면 되기 때문에 DP가 유리하다.
package day0331;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class MakeOne {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static StringTokenizer st;
static int max_cnt = Integer.MAX_VALUE;
static void func(int X, int cnt) {
if(cnt >= max_cnt) {
return;
}
if(X == 1 && cnt < max_cnt) {
max_cnt = cnt;
}
if(X % 3 == 0) func(X / 3, cnt + 1);
if(X % 2 == 0) func(X / 2, cnt + 1);
func(X - 1, cnt + 1);
}
public static void main(String[] args) throws IOException {
int X = Integer.parseInt(br.readLine());
/*func(X, 0);
bw.append(max_cnt + "");
bw.flush();
*/
int[] DP = new int[X + 1]; // DP 테이블
for (int i = 2; i <= X; i++) {
int min = 1 + DP[i - 1];
if (i % 3 == 0 && 1 + DP[i / 3] < min) min = 1 + DP[i / 3];
if (i % 2 == 0 && 1 + DP[i / 2] < min) min = 1 + DP[i / 2];
DP[i] = min;
}
System.out.println(DP[X]);
}
}
Author And Source
이 문제에 관하여(BJ1463 1로 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mraz0210/BJ1463-1로-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)