[2166]Greedy(1まで)

8416 ワード
greedy Java テキストリンク

[1になるまで]


<質問>
任意の数Nが1である前に、次の2つのプロセスのうちの1つを繰り返し選択して実行します.ただし,2番目の演算はNをKで割った場合にのみ選択できる.
Nから1を引く.
NをKで割る.
NとKが与えられると、Nが1になるまで1回または2回のプロセスを実行する最小回数を求めるプログラムを作成します.
<入力条件>
第1行N(2<=N<=10000)、K(2<=K<=10000)はスペースで区切られ、それぞれ自然数で与えられる.このとき入力されるNは常にK以上である.
＜出力条件＞
1行目Nが1になる前に1回または2回の処理を行わなければならない回数の最大値を出力する.
入力:255
出力:2
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();
    int result = 0;

    while(true) {
      if(n%k==0){
        n = n/k;
        result++;
      }
      else {
        n -= 1;
        result++;
      }
      if(n<k) break;
    }
    System.out.println(result); 
  }
}
問題の中でNの範囲は10万なので、1つ1つの問題を排除することができます.しかし,Nが100億以上の大数であると仮定すると,素早い動作をするには,NをKの倍数だけ効率的に減算することで行うことができる.
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    // N, K를 공백을 기준으로 구분하여 입력 받기
    int n = sc.nextInt();
    int k = sc.nextInt();
    int result = 0;

    while (true) {
      // N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
      int target = (n / k) * k;
      result += (n - target);
      n = target;
      // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
      if (n < k) break;
      // K로 나누기
      result += 1;
      n /= k;
      }

      // 마지막으로 남은 수에 대하여 1씩 빼기
      result += (n - 1);
      System.out.println(result);
      }
}
整列プログラム[3]ファイル名
4.5シンボル定数とプリプロセッサ#define