BOJ 1107번
수빈이는 현재 TV채널 100번을 보고있다. 리모컨으로 채널을 변경할 수 있는데, 리모컨에는 0부터 9까지 숫자버튼과 +버튼, -버튼이 있다. 리모컨이 일부 고장나서 숫자버튼 중 몇개가 고장난 상태이다.
현재 채널에서 채널 N으로 이동하기 위한 버튼 클릭 횟수를 출력하시오.
풀이 알고리즘 : 완전탐색
먼저 고장난 숫자버튼을 canuse 배열에 저장해서 해당 버튼을 사용할 수 있는지 확인한다.
그리고 채널 N은 최대 500000까지의 정수이다.
채널 100에서 채널 N으로 이동하는 방법 중에, N보다 큰 정수에서 -버튼을 계속 눌러서 채널 N으로 이동할 수 있는 경우가 있으므로, 완전탐색의 범위는 1부터 1000000까지 진행한다.
각각의 정수에 대해서, move[i]는 채널 i로 바로 이동했을 때 최소 거리이다.
채널 i를 이루는 숫자가 모두 사용할 수 있는 경우, 각각의 숫자 버튼을 누르는 횟수와 채널 100번에서 (+, -) 버튼만 이용해서 누른 횟수 중 최솟값으로 정의할 수 있다.
즉, move[i] = min( '채널의 길이', abs(100 - i) )
숫자 버튼이 고장나서 채널 i로 이동할 수 없는 경우, move[i]는 채널 100번에서 (+, -) 버튼만 이용해서 누른 횟수로 일단 정의할 수 있다.
즉, move[i] = abs(100 - i)
이후 1부터 1000000까지의 정수 i에 대해,
채널 100번에서 i번으로 이동 후, i번에서 채널 N번으로 이동하는 경우와, 현재 계산한 경우 두가지 중에 최솟값으로 계속해서 최신화시켜준다.
이후 마지막에 move[N]을 출력하면 답이다.
구조가 플로이드-와샬 알고리즘처럼, 중간 노드를 거쳐가는 경우가 더 짧으면 그것으로 변경하는 구조와 닮은 문제였다.
소스코드 보기
더보기
#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))
// 기본설정
typedef long long ll;
using namespace std;
int dirx[4] = {1, 0, -1, 0};
int diry[4] = {0, 1, 0, -1};
// 전역변수
int movei[1000000 + 1];
int main(void) {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
// 초기화
string n; cin >> n;
int m; cin >> m;
bool canUse[10];
memset(canUse, true, sizeof(canUse));
memset(movei, 0, sizeof(movei));
for(int i = 0; i < m; i++) {
int btn; cin >> btn;
canUse[btn] = false;
}
// 완전탐색
for(int i = 0; i < 1000000 + 1; i++) {
string channel_s = to_string(i);
bool directMove = true;
for(int j = 0; j < channel_s.size(); j++) {
directMove = directMove && canUse[channel_s[j] - '0'];
}
if(directMove) {
movei[i] = min((int)(channel_s.size()), abs(100 - i));
} else {
movei[i] = abs(100 - i);
}
}
int minmove = 1000000 + 1;
// 최소 버튼 클릭횟수 계산
for(int i = 0; i < 1000000 + 1; i++) {
int curmove = min(movei[i] + abs(i - stoi(n)), movei[stoi(n)]);
if(curmove < minmove) {
minmove = curmove;
}
}
cout << minmove;
return 0;
}
'백준_BOJ > BOJ (골드)' 카테고리의 다른 글
[백준/알고리즘] 9663번 N-Queen (골드 5) (0) | 2020.06.16 |
---|---|
[백준/알고리즘] 1799번 비숍 (골드 2) (0) | 2020.06.16 |
[백준/알고리즘] 9019번 DSLR (골드 5) (0) | 2020.06.16 |
[백준/알고리즘] 1963번 소수경로 (골드 5) (0) | 2020.06.13 |
[백준/알고리즘] 2688번 줄어들지 않아 (골드 5) (2) | 2020.06.01 |