티스토리 뷰
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
풀이
- 반례가 엄청 많이 존재하니 혹시라도 틀렸다면 질문게시판의 반례모음집 게시글을 참조하며 고쳐나가면 좋다.
- 어떻게 풀지 생각하다 BFS N부터 시작해서 100까지 가는 방법을 찾았다.
문제 분류는 브루트포스로 되어있는데 말 그대로 브루트포스로 0부터 1000000까지 모든 경우를 계산하는 방법도 있다.
- N에서 출발하는데 현재 숫자가 누를 수 있는 번호이면 (
isPossibleToPress(int n)
으로 각 자릿수에 누를 수 없는 수가 있는지 찾기) 해당 숫자에 도달하기까지의 카운트 값을 저장하고 리턴한다.- 이때 |이미 저장된
누를 수 있는 번호
- N| 보다 |누를 수 있는 번호
- N|값이 작거나 같고 카운트 값도 작거나 같을 경우에만 업데이트한다.
- 이때 |이미 저장된
- 누를 수 없다면 +1, -1 조작을 통해 갈 수 있으면 큐에 넣고 카운트를 1 증가시킨다.
- 이때 현재 숫자가
UPPER_BOUND
이면 +1을 하지 말고 넘기고 0이면 -1을 하지 말고 넘긴다.
- 이때 현재 숫자가
- 마지막에 답을 출력할 때 현재 카운트 값을 아래 세 값중 가장 작은 값으로 업데이트 한다.
- 현재 카운트 값 + |
누를 수 있는 번호
- 100| - 현재 카운트 값 + |
누를 수 있는 번호
의 자릿수| - |N - 100|
- 현재 카운트 값 + |
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M, res, ans;
static boolean[] brokenBtn = new boolean[10];
static Map<Integer, Boolean> visited = new HashMap<>();
static final int UPPER_BOUND = 1000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
ans = res = UPPER_BOUND;
if (M > 0) {
st = new StringTokenizer(br.readLine());
for (int i = 0; i < M; i++)
brokenBtn[Integer.parseInt(st.nextToken())] = true;
}
if (N == 100) bw.write(String.valueOf(0));
else {
solve();
ans += Math.min(Math.abs(100 - res), Integer.toString(res).length());
ans = Math.min(Math.abs(100 - N), ans);
bw.write(String.valueOf(ans));
}
br.close();
bw.close();
}
public static void solve() {
Queue<Num> q = new LinkedList<>();
q.offer(new Num(N, 0));
while (!q.isEmpty()) {
int num = q.peek().num;
int cnt = q.peek().cnt;
q.poll();
if (isPossibleToPress(num)) {
if (Math.abs(num - N) <= Math.abs(res - N) && cnt <= ans && num < res) {
res = num;
ans = cnt;
}
// System.out.println("num, cnt = " + num + ", " + cnt);
continue;
}
int nextNum = num + 1;
if (nextNum == UPPER_BOUND) continue;
if (visited.get(nextNum) == null) {
visited.put(nextNum, true);
q.offer(new Num(nextNum, cnt + 1));
}
if (num == 0) continue;
nextNum = num - 1;
if (visited.get(nextNum) == null) {
visited.put(nextNum, true);
q.offer(new Num(nextNum, cnt + 1));
}
}
}
public static boolean isPossibleToPress(int n) {
String num = Integer.toString(n);
for (int i = num.length() - 1; i >= 0; i--) {
int digit = Character.getNumericValue(num.charAt(i));
if (brokenBtn[digit]) return false;
}
return true;
}
static class Num {
int num;
int cnt;
public Num(int num, int cnt) {
this.num = num;
this.cnt = cnt;
}
}
}
'알고리즘' 카테고리의 다른 글
[백준] 7682. 틱택토 (Java) (0) | 2021.09.16 |
---|---|
문자열 문제풀이에 유용한 replaceAll(), matches() (ft. 정규표현식) (0) | 2021.09.09 |
[백준] 9019. DSLR (Java) (0) | 2021.08.16 |
[백준] 19238. 스타트 택시 (Java) (0) | 2021.08.16 |
[백준] 1976. 여행가자 (Java) (0) | 2021.08.09 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- CustomHook
- 시뮬레이션
- 해시
- 삼성역테기출
- 문자열
- 정규식
- BigInteger
- 구현
- 브루트포스
- 벨만포드
- 백준
- BFS
- Validation
- 그래프
- 다익스트라
- swea
- REACT
- regex
- 우선순위큐
- form
- 이분탐색
- matches
- java
- web
- 프로그래머스
- dfs
- 알고리즘
- dp
- 백트래킹
- vue.js
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
글 보관함