問題
https://atcoder.jp/contests/abc099/tasks/abc099_c
質問内容
問題は上記のリンクの通りになっていて,自分の考え的には動的計画法をもちいてやるのかなと思ったのですが,三つ目のサンプルすら通りませんでした。頭で計算してみても自分のコードの取り出し方とは違った方法のときに最小の取り出し方になるのが分かったので,解けている方のコードやヒントを見てみたのですが,どちらをみてもなぜこの計算で答えが出るのか分からなかったので,仕組みを教えていただければと思い質問させていただきました。具体的には、次の箇所が分かりません。
Java
1for(int i = 0; i <= n; i++) { 2 int j = n - i; 3 int s = i; 4 int t = j; 5 int p = 0; 6 while(s > 0) { 7 p += (s % 6); 8 s /= 6; 9 } 10 while(t > 0) { 11 p += (t % 9); 12 t /= 9; 13 }
ACがでたコードの下に自分でかいたコードも載せさせていただきます。また、dpを用いたやり方も教えていただけると大変参考になりますので,よろしければ是非お願いします。
ACがでていたコード
Java
1import java.util.*; 2 3public class Main { 4 public static void main(String[] args) { 5 Scanner sc = new Scanner(System.in); 6 int n = sc.nextInt(); 7 int ans = n; 8 for(int i = 0; i <= n; i++) { 9 int j = n - i; 10 int s = i; 11 int t = j; 12 int p = 0; 13 while(s > 0) { 14 p += (s % 6); 15 s /= 6; 16 } 17 while(t > 0) { 18 p += (t % 9); 19 t /= 9; 20 } 21 ans = Math.min(ans, p); 22 } 23 System.out.println(ans); 24 } 25}
自分でかいたコード
Java
1import java.util.Scanner; 2public class StrangeBank { 3 public static void main(String[] args){ 4 Scanner scan=new Scanner(System.in); 5 int[] dp=new int[100000]; 6 dp[0]=scan.nextInt(); 7 int i=0; 8 while(true){ 9 int p=1; 10 int q=1; 11 while(p*6<dp[i]){ 12 p*=6; 13 } 14 while(q*9<dp[i]){ 15 q*=9; 16 } 17 if(dp[i]>=9){ 18 dp[i+1]=Math.min(dp[i]-p,dp[i]-q); 19 } 20 else if(dp[i]>=6){ 21 dp[i+1]=dp[i]-6; 22 } 23 else{ 24 dp[i+1]=dp[i]-1; 25 } 26 27 if(dp[i+1]==0) break; 28 i++; 29 } 30 System.out.println(i+1); 31 32 } 33}
回答3件
あなたの回答
tips
プレビュー