[アルゴリズム]Java/標準/12852の使用
[アルゴリズム]Java/標準/12852の使用
質問する
質問リンク
方法
3つの演算結果がkであると仮定すると,Nからkまでの距離の最大値を求めるためにdpを用いる.
dpにおける点火式は以下の通りである
//dp[i] => n부터 i까지의 최소 거리
dp[현재 수에 연산한 결과(ex temp/3)] > n부터 현재 수까지의 거리 + 1
また,dpの最小距離に更新すると,その数の親を親配列に格納し,後で1から逆ブラウズを開始し,1のメソッドに含まれる関数を得る.// parent[temp] => n부터 temp까지의 거리가 최소일 때 temp로 오기전의 수
コード#コード#import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main_12852 {
static int[] dp;
static int parent[];
static int minCnt;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
// 각 수를 찾아오는 최단거리를 저장
dp = new int[N+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[N] = 0; // N에서부터 시작
// 해당 수의 전 수를 저장
parent = new int[N+1];
parent[N] = N;
int temp = N;
minCnt = Integer.MAX_VALUE;
// 3으로 나누기, 2로 나누기, 1 빼기를 진행
dfs(temp,0);
// 1부터 역으로 부모를 찾아가기
int[] arr = new int[minCnt];
int subIdx = 1;
for(int i=minCnt-1;i>=0;i--) {
arr[i] = subIdx;
subIdx = parent[subIdx];
}
// 출력
StringBuilder sb = new StringBuilder();
sb.append(minCnt+"\n");
sb.append(N+" ");
for(int i=0;i<minCnt;i++) {
sb.append(arr[i]+" ");
}
System.out.println(sb);
}
public static void dfs(int temp, int cnt) {
if(minCnt <= cnt) return;
if(temp == 1) {
if(minCnt > cnt) minCnt = cnt;
}
if(temp % 3 == 0 && dp[temp/3] > cnt+1) {
parent[temp/3] = temp;
dp[temp/3] = cnt+1;
dfs(temp/3, cnt+1);
}
if(temp % 2 == 0 && dp[temp/2] > cnt+1) {
parent[temp/2] = temp;
dp[temp/2] = cnt+1;
dfs(temp/2, cnt+1);
}
if(temp-1 > 0 && dp[temp-1] > cnt+1) {
parent[temp-1] = temp;
dp[temp-1] = cnt+1;
dfs(temp-1,cnt+1);
}
}
}
Reference
この問題について([アルゴリズム]Java/標準/12852の使用), 我々は、より多くの情報をここで見つけました https://velog.io/@gandi0330/알고리즘-Java-백준-1로-만들기-2-12852テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol