[백준]1107번 리모콘 2️⃣
첫 번째로 푼 풀이 + 두 번째로 다시 풀어볼 때의 풀이가 추가되었다.
[백준]1107번 리모콘
(2:25... ㅋㅋㅋㅋㅋㅋ)
- 버튼 종류 : 0~9의 숫자, +(현재+1) , -(현재-1) 존재
- 채널0에서 '-'를 누름 —> 채널 변화 ❌
- 채널은 무한대 만큼 있으니 '+'에 대한 제한은 없는 상태.
- 목표 채널 : N번
- 주어지는 것 : 고장난 버튼
- 현재 채널 : 100
채널 N으로 이동하기 위해, [ 버튼을 최소 몇 번 ] 눌러야 하는지 구하는 프로그램 작성하기
- 고장난 버튼의 개수도 주어지네 (0개이상 10개 이하)
풀이 생각
- 이문제에서 채널의 이동은
- 1️⃣ 숫자버튼을 통해 → 특정 숫자로 바로 이동 : 숫자가 n 자리수면 n개의 버튼을 누르는게 된다.-> 그리고 그 특정숫자로부터 n 까지 +나 -버튼을 통해 이동한다. 이 모든 횟수를 더해야한다.
- 2️⃣ '+ '버튼 , '-'버튼 만을 통해 → "1"단위로의 이동
- 따라서 1번, 2번 경우중 더 적은 수를 택하는 것
누를 수 있는 숫자 버튼이 5 만 있다하고, target이 500이면
- 555로 이동후 -를 55번 하는게.
- +를 400번 하는 것 보다 덜 든다.
target이 101이면
- 숫자로 101을 누르면 -> 3개의 버튼을 누르는 것
- + 버튼을 한 번 누르기 -> 1개읩 버튼을 누르는 것
target이 98이면
- 숫자로 98 누르면 -> 2개의 버튼
- - 버튼 두 번 -> 2 개의 버튼 누르기
이외의 경우가 있나?? 선택의 경우
-
주어진 숫자버튼으로 target과 최대한 가까운 숫자 만들기 → ??? 아무래도 모든 경우의 숫자들에 대해 해 보아야 할 것 같다.
-
완전탐색? → 완전탐색으로 풀어도 괜찮은 편이다.
-
생각하고 있는 완전탐색 :
- 100이 n이 되는데, +1 이나 -1 만을 통해서 달성하는데, 버튼을 몇 번 눌러야 하는지 →simpleCnt로 저장한다. (+와 - 모두 고장나있는 경우라면 Integer.MAX_VALUE를 저장)
- n의 자리수가 c라고 한다면
- c-1자리의 최소 숫자부터 c+1자리의 max 숫자에 대하여, 현재 버튼으로 누를 수 있는 수인지를 확인한다.
- 누를 수 있는 수라면, ( 해당 수를 위해 누르는 버튼의 수 ) + (해당 수 부터 n까지 +1이나 -1 연산의 개수 ) → numbcnt라고 한다.
- 만들어지는 모든 수에 대하여 numbcnt와 simpleCnt를 비교하여 더 작은 값을 저장한다.
- c-1자리의 최소 숫자부터 c+1자리의 max 숫자에 대하여, 현재 버튼으로 누를 수 있는 수인지를 확인한다.
-
이러한 완전탐색이 가능한가? YES
현재 n의 제한 : 50만: 500000 -> 6자리수. 100만을 넘는 경우는 조사할 필요가 없다. 따라서 만약 n이 6자리수라면 -> 10000 부터 999999 까지만 조사하면 되기 때문에 완전탐색을 해도 100만을 넘지를 않는다. -
왜 n-1자리도, n+1자리도 봐야하는가?
target이 1. 999 인 경우 (n+1자리도 봐야하는 이유) 주어진 수가 1과 0만 있다면 1000을 만드는게 111을 만드는 것보다 더 좋을 거임. 따라서, target의 자리수 m 이라고 하면 m-1자리수 ~ m+1자리수를 모두 만들어 봐야 하나 - 만들어 볼 것인가 아니면 - m-1자리수 가장 작은 숫자 ~ max 숫자 해서, 각 자릿수에 고장난 번호가 있으면 그 번호를 버리기를 할 것인가 ----> 최대..5자리수 10000~ 99999 -----> 6자리수 : 100000~ 999999 --최대 50만이니, 100만 넘는 거는 안 봐도됨 2. target이 10000 인 경우인데 버튼 0이 고장나있는 경우 9999 에서 +1을 하는게 더 낫기 때문임.
-
-
이 문제에서는, 자리수를 직접 구하는 함수를 작성하는게 중요한 것 같다.
- 만약 생각을 덜 하고 싶어서 매 int를 String으로 변환하여 각 자리수가 무엇인지 확인하게 되면 매 번 String을 생성하게 되기 때문에 주의해 줄 필요가 있다.
package cote;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/*
* 1 10
* 1+ 1 = 2 -> 4 -> 8
* 1 2 4 8 -> 9, 10
*
*
* */
public class Main{
/*
* Integer형태로 10000 부터 99999 까지 검사하기를 하면
* 해당 int에 대한 연산을 수행 해야 한다. 그게 낫겠다
* */
public static int resMin = Integer.MAX_VALUE;
public static int n,m;
public static boolean[] numbers = new boolean[10];// 0~ 9 까지의 버튼
public static boolean[] op = new boolean[2]; // +1, -1
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
Arrays.fill(numbers,true);
Arrays.fill(op,true);
// 가능한 버튼정보를 어떻게 넣을까? -> char 형태로?
// +와 -가 있어서..
// 아니면 그냥 boolean table을 생성하여, 고장났는지 여부를 표시? -> 이 방법을 택함
if(m>0){
String nots = br.readLine();
String[] disabled = nots.split(" ");
for(String s : disabled) {
// 고장난 버튼은 -일 수도 +일 수도 있다.고 생각했다.
try {
int numb = Integer.parseInt(s);
numbers[numb]=false;
}catch(NumberFormatException e){
if(s.equals("+")){
op[0]=false;
}else{
op[1]=false;
}
}
}
}
}
public static void solve(){
int simplecnt =Integer.MAX_VALUE;
int numbcnt =Integer.MAX_VALUE;
int tempCnt= Integer.MAX_VALUE;
// 단순히 +나 - 연산으로 구할 수 있는 경우.
if(n==100) {
resMin =0;
return;
}
else if(n>100&&op[0]){ // n 이 100보다 크고, + 연산자가 고장나지 않은 경우
simplecnt = n-100;
}else if(n<100 && op[1]) simplecnt=100-n; // n이 100보다 작고, -연산자가 고장나지 않은 경우
tempCnt = simplecnt;
// n은 0이상 50만 이하일 수 있다.
String temp = Integer.toString(n);
// target의 자리수를 구한다.
int len = temp.length();
// target의 후보인 수들의 '자리수'를 초기화한다.
int len_min =len,len_max = len;
int min=0,max=0;
// 500000
if(len == 6){
// len-1 자리 부터 len 자리까지
len_min = len -2;
len_max = len;
}else{
// len-1 자리부터 len + 1 자리까지
len_min = len-2;
len_max = len+1;
}
// 만약 len 이 한 자리 수 -> min은 0부터 해야함
if(len_min<=0) min =0;
else{
min = (int)Math.pow(10,len_min);
}
// len_max = 5 면 99999 해야하니
// len_max = 6 이면 999999 으로 해야 하니
max = (int)Math.pow(10,len_max)-1;
// min부터 max까지의 정수들에 대해 완전탐색한다.
for(int i=min;i<=max;i++){
// i라는 숫자가 '숫자버튼을 눌러' 만들 수 있는 것인지 확인한다.
if((numbcnt=splitNumber(i))==Integer.MAX_VALUE) continue;
// i가 만들 수 있는 숫자인 경우 -> i에서 n 까지 몇 번의 + or - 연산을 해야하는지 구한다.
if(n==i) numbcnt+=0;
else if(n>i&&op[1]){
numbcnt+= (n-i);
}else if(n<i && op[0]) numbcnt+=(i-n);
// 구해진 numbcnt와 tempCnt를 비교한다. tempCnt는 simpleCnt(+로만 or -로만했을 때의 count개수)로 초기화되어있다.
tempCnt=Math.min(tempCnt,numbcnt);
}
// 버튼으로 숫자를 만들 수는 없는 경우, simpleCnt가 최소가 될테니 for문 밖에서도 Resmin을 업데이트 해줘야한다.
tempCnt=Math.min(tempCnt,numbcnt);
resMin=Math.min(resMin,tempCnt);
}
//최대 6번의 연산을 한다
// a_n의 정수의 각 자리수를 확인하여, 각 자리에 있는 숫자가 고장난 버튼인지확인한다.
public static int splitNumber(int a_n){
int res = Integer.MAX_VALUE;
int len = (int)Math.log10(a_n) +1;
if(a_n==0) len = 1;
// 구성요소중 고장 난 버튼이 있는지 체크한다.
int next =a_n;
int cur=0;
int mul=(int)Math.pow(10,len-1);
while(mul>9){
cur = next/mul;
if(numbers[cur]==false)return res;
next-= (cur*mul);
mul/=10;
}
cur = next%10;
if(numbers[cur]==false)return res;
return len;
}
public static void main(String[] args) throws IOException {
Setting();
solve();
System.out.println(resMin);
}
}문제의 조건은 +,-가 고장나는 경우는 포함되지 않는 것이었다.
그랬다..
다른 사람 풀이를 보고 느낀 점
- 다른 사람들 풀이를 보니, 전체 수가 100만이기 때문에 , 나처럼 min, max를 하지 않아도 충분히 풀리는 문제였다.
2021-09-20 다시 풀어볼 때
(0:40)
0~9 버튼 중 고장나는 버튼이 주어진다. → 해당 버튼은 누를 수 없다.
0 번에서 - 버튼을 누르면 채널은 변하지 않는다.
N번으로 이동하려 한다.
N번으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는가???
-
현재 채널은 100번이다.
-
N은 0이상 50만 이하이다.
-
고장 난 버튼의 개수는 0 이상 10 이하 → 모든 숫자 버튼이 고장 날 수도 있다.
- +,-로만 이동하게 될 것.
-
두 가지 경우를 생각 해 볼 수 있다.
- 숫자 버튼을 눌러서 X 번으로 이동한 후 +,-를 통하여 N번으로 가기
- +,- 버튼만을 이용하여 N번으로 이동하기
- 두 가지 경우 중 최소의 값을 선택하는 것이다.
-
주어진 숫자 버튼 중, N번에 가까운 숫자를 만들어야 한다.
- 이를 위해 브루트 포스를 할 것인가?
- 이것을 이런식으로 생각 해 볼 수 있다. [ 현재 숫자를 조합해서 특정한 숫자를 만든다 ] 라는 것 보다도 [ 특정 숫자를, 현재 숫자들을 조합해서 만들 수 있는가? ] 라는 접근법으로 접근할 수 있다.
- 따라서 , 문제에서 주어진 N은 0이상 50만 이하이기 때문에, 50만 가지를 완전탐색하는 것이 가능하다.
-
특정 숫자를, 현재 수자들을 조합해서 만들 수 있는가 ?
- 이를 위하여, 특정 숫자의 각 자리를 확인하는 과정이 필요하다.
50만이 아닌 100만이다
- 또 이 경우를 간과했다.
- N은 50만 까지가 가능하지만, 어떤 숫자의 고장으로 인해 50만보다 높은 숫자에서 "-"를 통하여 이동하는게 더 적은 수가 드는 경우가 있다.
- 그렇다면 50만 보다 큰 수 중 어느 정도의 숫자까지가 가능한가? 를 본다면, 100부터 +와 - 만으로 이동할 경우 50만까지 이동하는 경우가 있으니, 이 수보다는 작은 경우까지만 검증을 해야할것이다. 따라서 넉넉잡아 100만까지로 하는 것이다.
런타임에러(NullPointer)
- m이 0인 경우에도 br.readLine()으로 다음 라인을 받으려고 해서 생긴 문제였다.
최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main{
public static int n;
public static int m;
public static int min = Integer.MAX_VALUE; // 5000000 으로 해두 되겠다.
public static boolean[] broken = new boolean[10]; //고장난 버튼 -> false
public static void Setting() throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int temp=0;
n = Integer.parseInt(br.readLine());
m = Integer.parseInt(br.readLine());
Arrays.fill(broken,true); //모두 true로 초기화
if(m>0) {
st = new StringTokenizer(br.readLine());
for (int i = 0; i < m; i++) {
temp = Integer.parseInt(st.nextToken());
broken[temp] = false;
}
}
}
public static void solve(){
if(n==100) {
min = 0;
return;
}
// +, -만을 이용하여 이동하는 경우를 생각하기.
// 현재는 100번에 위치하고 있다. N번과의 차이를 절댓값으로 구한다.
min = Math.abs((100-n));
int cnt=0;
//완전탐색을 한다.
for(int t=0;t<=1000000;t++){
// t라는 채널로 이동가능한 경우 -> (100->t ) + ( t-> N ) 의 수를 계산하여 min 과 비교한다.
if((cnt=isPossible(t))<0)continue;
// 100 -> t 로 가는데 버튼은 cnt 번 누른다.
// t- > N 으로 가는데에는 이제 +,- 만을 이용한다.
cnt += Math.abs((t-n));
min = Math.min(min,cnt);
}
}
// t라는 숫자를 현재 생성 가능한지 살펴본다 + 생성가능한 경우, t의 자리수를 리턴한다.
public static int isPossible(int t){
// 각 자리수를 구한다.
int cur =t;
int num = 0;
int cnt =1;
// 1의 자리 수 부터 확인한다.
while(true){
num = cur % 10 ;
if(broken[num]==false) return -1;
cur /=10;
if(cur ==0) break;
cnt++;
}
return cnt;
}
public static void main(String[] args) throws IOException {
Setting();
solve();
System.out.println(min);
}
}Author And Source
이 문제에 관하여([백준]1107번 리모콘 2️⃣), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ynoolee/백준1107번-리모콘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
