BOJ/1107)リモコン

リモコン(1107)、Gold 5

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

問題を解く

これはブルートフォスアルゴリズムで解くことができる問題である.
まず考えられるチャンネル移動方法は次のとおりです.

1) 숫자(0-9)버튼을 통해 목표 채널에 도달
2) +/- 버튼을 통해 목표 채널에 도달
3) 숫자 버튼을 이용해 목표 채널에 가까운 채널로 이동 후, +/- 버튼 통해 목표 채널에 도달

🤔 チャネル移動の実装方法

まず出力値result変数を初期化します.
最も簡単な実装方法は2番(+/-ボタン)です.
int result = Math.abs(N - 100)
+/-ボタンは+1/-1ずつ移動します.したがって、ターゲット値から現在位置の値を減算すると、+/-キーを押す回数がわかります.
ターゲットチャネルが現在のチャネル(100回)より小さい可能性があるため、ターゲットチャネルを絶対値に変換することを忘れないでください.
次に、デジタルボタンを使用してターゲットチャネルに到達する方法について説明します.
ターゲットチャンネルの最高価格は500000ですが、実際にボタンは0から9なので押すことができるチャンネルは99999999です.
私たちの解題方法はブルートフォースなので、すべての状況を考慮しなければなりません.
完全探索のように0から9999999999まで探索を繰り返す.

🤔 障害ボタンに近いチャンネルを検索する方法

すべてのデジタルボタンをブラウズしながら、3回の方法(最近のチャンネルブラウズ後、+/-ボタンでターゲットチャンネルに到達)を同時に実行してみます.
まず、現在閲覧中のチャンネルをString変数として一時的に定義します.
また,途中で重複文を終了する必要があるか否かを判断するブール型変数isBreakを宣言することもできる.
すべてのチャンネルを参照しながら、次の内容を確認します.

1) 현재 탐색 중인 채널에 고장난 숫자 버튼이 포함되어 있는 경우
2) 현재 탐색 중인 채널로 이동 가능한 경우(고장난 버튼이 없음)

前者の場合、チャネルに移動できないため、isBreakをtrue値に変換し、重複文を終了して次のチャネルを参照する必要があります.
後者の場合は、現在閲覧中のチャンネルがターゲットチャンネルに近いチャンネルであることを確認し、結果を設定します.
方法は、任意の変数min内で現在閲覧中のチャンネルに移動するためにクリックする回数を記憶し、予め宣言されたresult変数と比較してresult値を両者の中で最も高い値に変更することである.

ランダム変数min(ボタンを押して現在のナビゲーションチャネルに移動する回数)を設定します.
int min = len + Math.abs(N - i)

lenは現在探索中のチャンネル長であり,2桁であれば2回押すことを意味する.次に、ボタンを押して+/-ターゲットチャンネルに到達するため、以下のようにして成立します.

で事前に宣言された結果値と比較して、結果変数をより小さな値に変更します.
result = Math.min(result, min)

Mathクラスのmin関数を使用して、結果変数を現在のチャネルの移動回数と結果格納の移動回数のより小さい値に更新します.
0から99999999まで、上記の手順を繰り返し、結果値を更新します.

ソースコード

public class BOJ1107 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        boolean[] broken = new boolean[10];
        // 고장난 버튼이 0개일 경우 입력 skip 처리 -> NP 방지
        if (M != 0) {
            String[] input = br.readLine().split(" ");
            for(int i = 0; i < M; i++)
                broken[Integer.parseInt(input[i])] = true;
        }
        br.close();
        
        int result = Math.abs(N - 100); // 2번 방법으로 초기화
        // 고장나지 않은 리모콘 버튼으로만 N과 가장 근사한 번호를 만든 후 +, - 로 이동하는 값 중의 최소값을 선택
        for(int i = 0; i <= 999999; i++) {
            String str = String.valueOf(i);
            int len = str.length();
            boolean isBreak = false;
	
            for(int j = 0; j < len; j++) {
                if(broken[str.charAt(j) - '0']) {
                    isBreak = true;
                    break;
                }
            }
            if(!isBreak) {
                int min = len + Math.abs(N - i);
                result = Math.min(min, result);
            }
        }
        System.out.println(result);
    }
}

ポスト

これは最も簡単で無知な方法であるが,ブルーフォースアルゴリズムの問題を多く解決したことがないため,近接する方法を見つけるのは難しい.
最大値500000にだまされて99999999まで、見逃すか見逃さないかが答えの鍵です.
その後,故障チャンネルを扱う方法もあり,探索中のチャンネルの長さを考慮し,移動回数を探すなどの考慮事項がある.
白い金色じゃない...いつになったら詳しい条件を確実に実行できるだろうか.