百駿1107草
16579 ワード
https://www.acmicpc.net/problem/1107
完全に探求問題だ.
入力したアクセスするチャンネルで作成できる最も近い数字を見つけ、++または--で実現しようとします.
このため、検索するチャンネルの各数字を抽出し、障害のないリモコンボタンと比較して、近い数字を生成する必要があります.しかし,この方法は変数が多く,状況も多いため,コードの記述が困難であり,正確な答えを保証することは困難である.
別の方法があるのか悩んだあげく、数学では解決できないという結論に至った.
だから私はBaek Junアルゴリズムの分類を見て、完全に探求問題です...
多くの不足を感じた瞬間だった.
完全探索だと分かっていても、すぐに解題に近づくことはできなかった.
与えられた問題を線形構造に構造化します.
適切な方法で解を構成するまで,構造化された問題空間を探索した.
編成された年を整理する.
ソース:https://hcr3066.tistory.com/26
問題を完全に探求するにはこのような方法で解決しなければならない.Googleで見つけたブログで
1番から適用すると、問題で希望のチャンネルを見つけるはずだったのですが、リモコンボタンが壊れていました.このため、リモコンボタンに障害が発生したボタンは、0~9のリストから削除できます.
また、検索するチャンネル範囲は0≦N≦500000であるため、完全閲覧範囲は0〜1000000である.なぜなら、500000チャンネルに行くには、100から探す方法があり、1000000から探す方法があるからです.
問題を線形構造に構造化します.次に構造化空間で答えを探します.まず最も見つけやすいチャンネルの方法は、探しているチャンネルNから100を減算し、++または--を加えることです.回数が正数なのでabsを与えます.
次に、ボタンを移動する方法で、保存ボタンのリストでボタンをクリックできる場合は、cntを増やして数字を検索できます.
どちらの場合も、小さな値を答えにすればいいのです.
追加の説明を注記した.
リモコン-フルナビゲーション
完全に探求問題だ.
入力したアクセスするチャンネルで作成できる最も近い数字を見つけ、++または--で実現しようとします.
このため、検索するチャンネルの各数字を抽出し、障害のないリモコンボタンと比較して、近い数字を生成する必要があります.しかし,この方法は変数が多く,状況も多いため,コードの記述が困難であり,正確な答えを保証することは困難である.
別の方法があるのか悩んだあげく、数学では解決できないという結論に至った.
だから私はBaek Junアルゴリズムの分類を見て、完全に探求問題です...
多くの不足を感じた瞬間だった.
完全探索だと分かっていても、すぐに解題に近づくことはできなかった.
与えられた問題を線形構造に構造化します.
適切な方法で解を構成するまで,構造化された問題空間を探索した.
編成された年を整理する.
問題を完全に探求するにはこのような方法で解決しなければならない.Googleで見つけたブログで
1番から適用すると、問題で希望のチャンネルを見つけるはずだったのですが、リモコンボタンが壊れていました.このため、リモコンボタンに障害が発生したボタンは、0~9のリストから削除できます.
また、検索するチャンネル範囲は0≦N≦500000であるため、完全閲覧範囲は0〜1000000である.なぜなら、500000チャンネルに行くには、100から探す方法があり、1000000から探す方法があるからです.
問題を線形構造に構造化します.次に構造化空間で答えを探します.まず最も見つけやすいチャンネルの方法は、探しているチャンネルNから100を減算し、++または--を加えることです.回数が正数なのでabsを与えます.
次に、ボタンを移動する方法で、保存ボタンのリストでボタンをクリックできる場合は、cntを増やして数字を検索できます.
どちらの場合も、小さな値を答えにすればいいのです.
追加の説明を注記した.
import java.io.*;
import java.util.ArrayList;
public class Main {
static int n, s;
static int count = 0;
static ArrayList<Integer> btn;
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String num = br.readLine();
int len = num.length();
n = Integer.parseInt(num);
int m = Integer.parseInt(br.readLine());
btn = new ArrayList();
for (int i = 0; i < 10; i++) {
btn.add(i);
}
//고장난 버튼들을 저장
ArrayList broken = new ArrayList();
//만약 m이 0, 즉 고장난 버튼이 0개일 경우 입력을 받지 말아야한다. 이 부문 처리를 안해 처음에 틀렸다.
if (m != 0) {
String[] line = br.readLine().split(" ");
for (int i = 0; i < m; i++) {
broken.add(Integer.parseInt(line[i]));
}
}
//전체 버튼 중 고장난 버튼을 제외
if(m != 0) {
for (Object a : broken) {
Integer t = (Integer) a;
btn.remove(t);
}
}
//시작 위치에서 해당 채널로 ++ 또는 --로만 가는 횟수
int ans = Math.abs(n - 100);
//0부터 1000000까지 모든 채널을 탐색해서 N까지 가는 횟수 구하기
for (int i = 0; i <= 1000000; i++) {
//solution 함수에서 i채널로 이동 가능한지 불가능한지 검사
int cnt = solution(i);
if(cnt>0)
// 둘 중 최소를 선택
//i채널에서 n채널로 가는 횟수+i채널의 길이와 현재 ans값 중 최소값
ans = Math.min(ans, Math.abs(n-i)+cnt);
}
bw.write(ans + "\n");
br.close();
bw.close();
}
private static int solution(int n) {
int cnt = 0;
//n==0일 경우와 아닌 경우 분리
if (n == 0) {
//0이 고장났다면 0을 리턴, 해당 채널로는 이동이 불가능하다는 의미
if (!btn.contains(n))
return 0;
//그렇지 않다면 0채널로 이동한 것이 되니 길이인 1을 리턴
else
return 1;
}
while (n > 0) {
//n의 자릿수 중 하나라도 btn에 포함되어 있지않다면 해당채널로 가는 것은 불가능하기때문에 0을 리턴
if(!btn.contains(n%10))
return 0;
//그 외에는 cnt를 증가시키고 다시 다음 자릿수를 뽑아 반복한다.
cnt++;
n = n/10;
}
return cnt;
}
}
Reference
この問題について(百駿1107草), 我々は、より多くの情報をここで見つけました https://velog.io/@estry/백준-1107-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol