코딩테스트/BOJ

[BOJ] 1107 리모컨 - JAVA

5월._. 2023. 6. 15.
728x90

1. 문제

 

1107번: 리모컨

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다.  둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼

www.acmicpc.net

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 
수빈이가 지금 보고 있는 채널은 100번이다.


2. 풀이

조합 이용

Main

카운트를 저장할 int배열(dp)를 만든다. 그 크기는 50만의 두배로 정한다.

배열을 INF로 채운다.

고장난 버튼이라면 remote[번호]에 true를 저장한다.

find메서드를 호출한다.

dp[100]에 0을 저장하고 answer에 diff + Math.min(dp[N-diff], dp[N+diff])를 저장한다. (diff가 절댓값이기 때문에)

answer와 Math.abs(100-N)을 비교한다. (100번부터 +,-만으로 N에 도달하는 경우)

static int[] dp;
static boolean[] remote;
static int INF = 1_000_000;
static int diff = INF;
static int N;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   N = Integer.parseInt(in.readLine());
   int M = Integer.parseInt(in.readLine());
   remote = new boolean[10];
   dp = new int[INF];
   Arrays.fill(dp,INF);
   if(M !=0){
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<M;i++) remote[Integer.parseInt(st.nextToken())] = true;
   }

   find(0,0);
   dp[100] = 0;
   int answer = diff;
   if(N+diff < INF) answer += N >= diff ? Math.min(dp[N+diff],dp[N-diff]):dp[N+diff];
   answer = Math.min(answer, Math.abs(100-N));
   System.out.println(answer);
}

 

조합

6자리를 뽑았다면 멈춘다.

next에 num*10+i를 저장한다.

만약 불가능한 번호이거나(remote[i]), dp[next]에 이미 값이 있다면 넘긴다.

dp[next]에 cnt+1을 저장한다.

Math.abs(N-next)와 diff를 비교해서 더 작은 값을 diff에 넣는다.

next가 0이 아닐때만 재귀 호출한다.(001,002같은 경우의 수 차단)

public static void find(int cnt, int num) {
   if(cnt>=6){
      return;
   }

   int next;
   for(int i=0;i<10;i++){
      next = num*10+i;
      if(remote[i] || dp[next] != INF) continue;
      dp[next] = cnt+1;
      diff = Math.min(diff, Math.abs(N-next));
      if(next!=0) find(cnt+1, next);
   }
}

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_1107_리모컨 {
   static int[] dp;
   static boolean[] remote;
   static int INF = 1_000_000;
   static int diff = INF;
   static int N;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(in.readLine());
      int M = Integer.parseInt(in.readLine());
      remote = new boolean[10];
      dp = new int[INF];
      Arrays.fill(dp,INF);
      if(M !=0){
         StringTokenizer st = new StringTokenizer(in.readLine());
         for(int i=0;i<M;i++) remote[Integer.parseInt(st.nextToken())] = true;
      }

      find(0,0);
      dp[100] = 0;
      int answer = diff;
      if(N+diff < INF) answer += N >= diff ? Math.min(dp[N+diff],dp[N-diff]):dp[N+diff];
      answer = Math.min(answer, Math.abs(100-N));
      System.out.println(answer);
   }
   public static void find(int cnt, int num) {
      if(cnt>=6){
         return;
      }

      int next;
      for(int i=0;i<10;i++){
         next = num*10+i;
         if(remote[i] || dp[next] != INF) continue;
         dp[next] = cnt+1;
         diff = Math.min(diff, Math.abs(N-next));
         if(next!=0) find(cnt+1, next);
      }
   }
}

 

브루트포스 이용

Main

채널 0부터 1_000_000까지 전부 돌려가면서 리모컨으로 누를 수 있는 숫자인지 파악한다.

누를 수 있는 채널이라면 그 채널과 N의 차이에 채널의 자릿수를 더한 것과 answer을 비교해서 더 작은 값을 answer에 넣는다.

answer의 초기값은 100번에서 N까지 +,-버튼만을 이용해서 도달한 값이다.

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

   remote = new boolean[10];
   if(M !=0){
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<M;i++) remote[Integer.parseInt(st.nextToken())] = true;
   }

   int answer = Math.abs(100-N);

   for(int channel=0;channel<=1_000_000;channel++){
      int cnt = count(channel);
      if(cnt==0) continue;
      answer = Math.min(answer, cnt + Math.abs(channel-N));
   }

   System.out.println(answer);
}

 

count

리모컨으로 누를 수 있는 채널인지 확인하고 버튼 몇 개를 눌러야 하는지 반환한다.

0이면 바로 remote[0]을 확인하고, 0보다 크면 10으로 나눠가면서 나머지 값이 고장난 버튼이 아닌지 확인한다.

public static int count(int channel){
   if(channel==0) return remote[0]?0:1;
   int cnt = 0;
   while(channel>0){
      if(remote[channel%10]) return 0;
      cnt++;
      channel/=10;
   }
   return cnt;
}

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_1107_리모컨2 {
   static boolean[] remote;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int N = Integer.parseInt(in.readLine());
      int M = Integer.parseInt(in.readLine());

      remote = new boolean[10];
      if(M !=0){
         StringTokenizer st = new StringTokenizer(in.readLine());
         for(int i=0;i<M;i++) remote[Integer.parseInt(st.nextToken())] = true;
      }

      int answer = Math.abs(100-N);

      for(int channel=0;channel<=1_000_000;channel++){
         int cnt = count(channel);
         if(cnt==0) continue;
         answer = Math.min(answer, cnt + Math.abs(channel-N));
      }

      System.out.println(answer);
   }

   public static int count(int channel){
      if(channel==0) return remote[0]?0:1;
      int cnt = 0;
      while(channel>0){
         if(remote[channel%10]) return 0;
         cnt++;
         channel/=10;
      }
      return cnt;
   }
}

3. 결과

INF값을 10_000_000으로 했다가 1_000_000으로 해도 가능한 걸 깨닫고 바꿨더니 메모리나 시간면에서 확실히 줄어들었다.(50940KB, 184ms -> 15764KB,112ms)

하지만 이 문제는 브루트포스로 푸는게 가장 빠르고 쉽게 푸는 방법인 것 같다.

'코딩테스트 > BOJ' 카테고리의 다른 글

[BOJ] 9019 DSLR - JAVA  (0) 2023.06.17
[BOJ] 7662 이중 우선순위 큐 - JAVA  (0) 2023.06.16
[BOJ] 14940 쉬운 최단거리 - JAVA  (0) 2023.06.14
[BOJ] 12852 1로 만들기 2 - JAVA  (0) 2023.06.13
[BOJ] 12101 1,2,3 더하기 2 - JAVA  (0) 2023.06.12

댓글