1107 리모컨

리모컨 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	14448	3208	2237	22.363%

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 

수빈이가 지금 보고 있는 채널은 100번이다.

입력

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

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

이 문제는 예전에 C++으로 풀었던 적이 있는데 파이썬으로도 풀어보고 싶어졌다.

아래는 C++로 풀었을 때의 코드이다.

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdio>

using namespace std;

bool channel[10];

int check(int i);

int main()

{

ios_base::sync_with_stdio(false);

    //freopen("input.txt","r",stdin);

int N, M;

cin >> N >> M;

memset(channel,false,sizeof(channel));

for(int i=0; i<M; i++)

{

int num;

cin >> num;

channel[num] = true;

}

int result = abs(N-100);

for(int i=0; i<=1000000; i++)

{

int len = check(i);

if(len != 0)

{

result = min(result,len+abs(N-i));

}

}

cout << result << '\n';

return 0;

}

int check(int i)

{

    string str = to_string(i);

    int len = str.length();

    int count=0;

    for(int i=0; i<len ; i++)

    {

        if( channel [ int(str.at(i)-'0') ] == true )

        {

            return 0;

        }

        else

        {

            count++;

        }

    }

    return count;

}

코드에서 보았듯이 0부터 최대 채널 수까지 카운팅해가며

고장나지 않은 채널들로 구성할 수 있는지를 체크하는 방법이다.

그러나 이번 파이썬으로는 조금 다르게 풀어보았다.

import sys

sys.stdin = open("input.txt","r",encoding="utf-16")

remote_controller = ['0','1','2','3','4','5','6','7','8','9','+','-']

goal_channel = int( input() )

num_malfun = int( input() )

malfun_list=[]

if num_malfun != 0:

malfun_list = list(input().split())

for i in malfun_list:

remote_controller.remove(i)

cur_channel = 100

# only + or -

only_up_down = None

if goal_channel >= cur_channel and '+' in remote_controller:

only_up_down = goal_channel - cur_channel

elif goal_channel < cur_channel and '-' in remote_controller:

only_up_down = cur_channel - goal_channel

# +,- and channel btn

use_anything = [500000]

if remote_controller != ['+','-']:

permutation_length = len(str(goal_channel))

permutations = set()

temp = [''] * permutation_length

remote_controller_only_btn = list(remote_controller)

remote_controller_only_btn.remove('+')

remote_controller_only_btn.remove('-')

def make_permutation(deepness, length):

if deepness == length:

if only_up_down > abs(goal_channel-int(''.join(temp))):

permutations.add( ''.join(temp) )

else:

for i in remote_controller_only_btn:

temp[deepness] = i

make_permutation(deepness+1,length)

for i in range(-1,2,1):

if permutation_length+i <1:

continue

else:

temp = [''] * (permutation_length+i)

make_permutation(0,permutation_length+i)

try:

permutations.remove( "0"*(permutation_length+i) )

permutations.add("0")

except:

pass

if permutations != set():

permutations = map(lambda x : abs( int(x) - goal_channel)

, permutations)

m = min(permutations)

use_anything.append( m + permutation_length+i )

permutations= set()

print( min( [only_up_down, min(use_anything)] ) )

먼저 채널버튼으로만 이동할 수 있는 최솟값을 구하고.

고장나지않은 버튼으로 목표로 하는 채널자릿수 +-1 만큼 총 3가지의 자리의 순열들을 만들고

채널버튼으로만 이동할 수 있는 최솟값이랑 비교하여 더 작을 경우 저장한다.

이렇게 순열로 만든 값들중에 최솟값을 구한다.

메모리와 시간이 엄청 많이 들지만 다른 방법으로 풀었다는 것에 의의를 두면 좋을 것 같다.