목차
문제
https://www.acmicpc.net/problem/1107
수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.
리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.
수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.
수빈이가 지금 보고 있는 채널은 100번이다.
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다.
풀이
전형적인 재귀 함수 사용 문제이다.
버튼을 누를 수 있는 경우의 수를 remote[] 배열에 저장했고,
1자리부터 6자리(최대 500000이므로)의 버튼을 누른다 가정하고 모든 경우의 수를 판단했다.
최악의 경우에도 시간 복잡도가 2초 내에 해당할 수 있을 것이라 판단했다.
자세한 내용은 주석을 참고할 것.
코드
import java.io.*;
import java.util.*;
/*
1. 먼저 M개에 맞는 채널 개수만큼 입력
2. 해당 채널이 결과값과 얼마나 차이나는지 확인
3. 백트래킹 사용
최대 N = 500000 .. 6자리
경우의 수 : 10^6 = 1000000
5자리, 4자리 .. 가 더욱 효율적일 수도 있다. 결국 다 구해봐야 한다.
*/
class Main {
static final int CHANNAL = 100;
static int N;
static int M;
static int remote[];
static int result; //결과
public static void main(String[] args) throws Exception{
//입력
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
HashSet<Integer> broken = new HashSet<Integer>();
//고장난 버튼이 있다면 추가하기
if(M > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) broken.add(Integer.parseInt(st.nextToken()));
}
//리모컨 버튼 누를 수 있는 경우를 담는 배열
remote = new int[10 - M];
int idx = 0;
for(int i = 0; i < 10; i++) {
if(broken.contains(i)) continue;
remote[idx++] = i;
}
// +1 -1만 했을 때 나오는 결과
result = Math.abs(N - CHANNAL);
//리모컨 누르는 회수(1자리 ~ 6자리)
for(int i = 1; i <= 6; i++) {
solve(i, 0, 0);
}
System.out.println(result);
}
static void solve(int maxButtonCount, int nowButtonCount, int totalCount) {
if(maxButtonCount == nowButtonCount) { //버튼 총 사용량 체크
result = Math.min(result, Math.abs(totalCount - N) + maxButtonCount);
return;
}
totalCount *= 10; //자리수 추가
for(int i = 0; i < remote.length; i++) {
solve(maxButtonCount, nowButtonCount + 1, totalCount + remote[i]);
}
}
}
'알고리즘 > 백준' 카테고리의 다른 글
1260 - DFS와 BFS[S2] (0) | 2023.12.05 |
---|---|
2606 바이러스[S3] (1) | 2023.11.11 |
16236 - 아기상어(G3) (0) | 2023.11.02 |
17144 - 미세먼지 안녕(G4) (0) | 2023.11.02 |
1780 - 종이의 개수(S2) (0) | 2023.11.02 |