Link https://www.acmicpc.net/problem/1107
Note
어떤 멍청이가 버튼을 너무 세게 누르는 바람에 버튼이 고장나서 내가 원하는 채널로 갈때 내가 버튼을 몇번 눌러야 하는지 계산 하는 문제
왜 고장을 낸건지 너무 화가난다.
처음으로 백준 게시판에 안된다고 반례 찾아달라고 질문 올린 문제, 테스트케이스만 30개 이상 돌려본거 같다.
접근을 3가지 방법으로 해야한다
1. 현재 채널에서 목표 채널까지 + , - 을 눌러서 최소로 가는 경우
2. 목표 채널보다 작으면서 최대인 경우
3. 목표 채널보다 크면서 최소인 경우
3가지 방법중에 최소인 경우를 구해야 한다.
또한 0000 의 경우에는 0을 한번 누른거와 같기 때문에 앞에 들어가는 0의 개수를 세야 한다.
연산이 끝났을 경우 몇번을 눌러야 하는지는 |목표채널 - 근접채널| + 근접채널의 자리수 - 앞에 등장하는 0의 개수 로 정해진다.
또한 목표 채널이 4자리 수라고 해서 무조건 4자리 수에서 답을 찾는게 아닌 3 ~ 5 자리 사이에서 답을 찾아야 한다.
목표 채널이 최대 500,000 이지만 채널이 최대 500,000까지 있는게 아니다, 채널이 무한정 있다고 생각하고 풀어야 한다.
하지만 목표 채널이 최대 500,000이고 시작 채널 100에서 +, - 만 가지고 하는 경우 499,000 이기 때문에 999,000 이상의 채널은
검색하는 조건이 의미가 없다. 따라서 최대 채널은 999,999까지만 설정해도 무방하다.
알고리즘
- 목표 채널, 고장난 버튼의 수, 고장난 버튼 들을 입력 받는다.
- 목표 채널의 자리수가 6자리 미만이면서 1이 고장이 나지 않았다면 목표 채널보다 1자리 늘려서 탐색을 한다.
- 1이 고장난 경우 목표 채널 자리수 만큼에서의 최소값보다 작을 수 없기 때문. - 0을 포함해 9개만 고장난 경우거나 전부 고장난 경우가 아니면 현재 자리 수 만큼 탐색을 한다.
3 - 1. 현재 자리수가 2자리 이상인 경우 현재 자리수보다 1자리 적은 경우를 탐색 한다. - 최소값을 출력한다.
탐색 알고리즘
1. 0번부터 탐색하는 자리의 수만큼 반복을 진행한다.
2. numbers 배열 pos 자리에 순차적으로 사용 가능한 버튼을 넣고 다음 자리로 진행한다.
3. pos가 목표하는 자리 수에 도착한다면 numbers 배열에 들어있는 값들을 10진수로 구체화 한다.
4. numbers배열에서 불필요한 0들의 개수를 센다. ( 0070의 경우 00은 없어도 되는 경우 따라서 값은 2 )
5. |목표 채널 - 구해진 채널| - 불필요한 0의 수 + 채널의 자리수 를 최소 채널 수와 비교한다.
소스코드
#include <iostream>
#include <cmath>
#include <string.h>
using namespace std;
bool ableButton[10];
int digits[6];
int digitsLength;
int myMin;
int target;
void func(int pos, int numbers[6], int caseType)
{
if (pos == digitsLength + caseType)
{
int zeroCount = 0;
for (int zPos = pos - zeroCount - 1; zPos > 0 && numbers[zPos] == 0; zPos--) zeroCount++; // 시작이 0 인 경우
int sum = 0;
for (int i = pos - 1; i >= 0; i--) // 값 계산
{
sum *= 10;
sum += numbers[i];
}
int count = pos + abs(sum - target) - zeroCount; //값 차이 계산
//cout << sum << " : " << count << " , " << zeroCount << endl;// For debug
if (myMin > count)
myMin = count;
}
else
{
for (int i = 0; i < 10; i++)
{
if (ableButton[i] == false) // 고장난 경우는 탐색하지 않음
continue;
numbers[pos] = i;
func(pos + 1, numbers, caseType);
}
}
}
int main()
{
memset(ableButton, true, sizeof(ableButton)); // 배열 초기화
int out;
cin >> target >> out;
digitsLength = target == 0 || target == 1 ? 1 : log10(target) + 1;
for (int i = 0; i < out; i++) // 고장난 버튼 파악
{
int number;
cin >> number;
ableButton[number] = false;
}
int number = target;
for (int i = 0; i < digitsLength; i++) // 숫자 자리 분리
{
digits[digitsLength - i - 1] = number % 10;
number /= 10;
}
int numbers[6];
fill_n(numbers, 6, 0);
myMin = abs(target - 100); // 목표 채널 - 현재 채널 을 최소값으로 설정
if (ableButton[1] && digitsLength < 6) // 10만 미만의 경우 한자리를 더 늘려서 검색
func(0, numbers, 1);
if ((ableButton[0] == false && out == 9) || out < 10) // 0을 포함해 9개가 고장나거나, 전부 고장난 경우
{
func(0, numbers, 0);
if (digitsLength > 1)
func(0, numbers, -1);
}
cout << myMin;
return 0;
}
2019-01-15 16:49:33에 Tistory에서 작성되었습니다.
