PS/BOJ

1107: 리모컨 [틀렸습니다.]

전라남도교육지원청 2023. 9. 24. 18:25
 

1107번: 리모컨

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

www.acmicpc.net

풀이

#case

  1. 숫자 버튼 없이 +, - 버튼으로만 이동하는 경우 (채널을 바꾸지 않아도 되는 경우를 포함한다.)
  2. 누를 수 있는 버튼으로 이동하고자 하는 채널과 근사한 값들을 만들어 +, - 버튼으로 이동하는 경우
    • 자릿수가 같은 숫자로 출발하는 경우
    • 자릿수가 다른 숫자로 출발하는 경우 (예. 0, 1이 고장 났을 때 999에서 1000으로 이동)

 

#구현 방안

  1. 1행 입력값과 100의 차 구하기
    • 1행 입력값보다 큰 값으로 만들기
    • 1행 입력값보다 작은 값으로 만들기
      • 앞자리부터 누를 수 있는 버튼인가 확인하기
      • 누를 수 있는 경우 모두 눌러준다.
      • 누를 수 없는 경우 바로 다음 버튼을 눌러주고 남은 자리는 모두 가장 작은/큰 버튼으로 채운다.
    • 근사값 만들기
      • 한 버튼만 누르고 모두 0으로 채워 가까운 값 찾기
      • 가장 앞에 있는 0을 다른 버튼으로 채워보고 가까운 값 찾기
      • 반복
    • 한 자리 큰 수 만들기
      • 0이 아닌 가장 작은 버튼을 한 번 누르고 나머지 모든 자리를 가장 작은 버튼으로 채운다.
    • 한 자리 작은 수 만들기
      • 0이 아닌 가장 큰 버튼을 한 번 누르고 나머지 모든 자리를 가장 큰 버튼으로 채운다.
using System;
using System.Collections.Generic;

class program
{
    static int ch = 100;
    static int N, M, near, up, down, large, small;
    static int[] click = new int[6];
    static List<int> button = new List<int>();
    static List<int> channel = new List<int>();
    static void Main()
    {
        for (int i = 0; i < 6; i++) click[i] = 0;

        N = int.Parse(Console.ReadLine());
        M = int.Parse(Console.ReadLine());
        for (int i = 0; i < 10; i++) button.Add(i);
        if (M > 0)
        {
            string[] broken = Console.ReadLine().Split();
            foreach (string s in broken) button.Remove(int.Parse(s));
        }
        channel.Add(N);

        int digit = N.ToString().Length;
        int square = 1;

        // 근사값 만들기
        int btn = button.Count;
        int low = 0; int high = 0;
        if (btn > 0)
        {
            low = button[0];
            high = button[btn - 1];
        }
        int[] compare = new int[btn];
        for (int i = 0; i < digit - 1; i++) square *= 10;
        for (int i = 0; i < 6; i++) click[i] = 0;

        near = ch;
        up = ch;
        down = ch;
        large = ch;
        small = ch;

        if (btn > 0)
        {
            while (square > 0)
            {
                for (int i = 0; i < btn; i++) compare[i] += square * button[i];
                for (int i = 0; i < btn; i++)
                {
                    if (compare[i] > N)
                    {
                        if (i > 0)
                        {
                            int j = 1;
                            for (; j < square; j = 10 * j + 1) ;
                            j /= 10;
                            int least = compare[i - 1] + j * high;
                            int most = compare[i] + j * low;
                            if (N - least < most - N)
                            {
                                for (int k = 0; k < btn; k++)
                                    compare[k] = compare[i - 1];
                            }
                            else
                            {
                                for (int k = 0; k < btn; k++)
                                    compare[k] = compare[i];
                            }
                        }
                        else
                        {
                            for (int k = 0; k < btn; k++)
                                compare[k] = compare[0];
                        }
                        break;
                    }
                    else if (i == btn - 1)
                    {
                        for (int k = 0; k < btn; k++)
                            compare[k] = compare[i];
                    }
                }
                square /= 10;
            }
            near = compare[0];
            click[1] = near.ToString().Length;

            if (btn > 1 && button[0] == 0)
            {
                up = button[1];
                for (int i = 0; i < digit; i++)
                    up = 10 * up + button[0];
                click[2] = digit + 1;
            }
            else if (button[0] != 0)
            {
                up = button[0];
                for (int i = 0; i < digit; i++)
                    up = 10 * up + button[0];
                click[2] = digit + 1;
            }

            if (button[btn - 1] != 0 && digit > 1)
            {
                down = button[btn - 1];
                for (int i = 2; i < digit; i++)
                    down = 10 * down + button[btn - 1];
                click[3] = digit - 1;
            }

        }

        if (btn > 1)
        {
            for (int i = btn - 2; i >= 0; i--)
            {
                if (int.Parse(N.ToString().Substring(0, 1)) >= button[i])
                {
                    large = button[i + 1];
                    for (int j = 1; j < digit; j++)
                    {
                        large *= 10;
                        large += button[0];
                    }
                    break;
                }
            }
            click[4] = large.ToString().Length;
        }

        if (btn > 1)
        {
            for (int i = 1; i < btn; i++)
            {
                if (int.Parse(N.ToString().Substring(0, 1)) <= button[i])
                {
                    small = button[i - 1];
                    for (int j = 1; j < digit; j++)
                    {
                        small *= 10;
                        small += button[btn - 1];
                    }
                    break;
                }
            }
            click[5] = small.ToString().Length;
        }

        click[0] += Math.Max(ch, N) - Math.Min(ch, N);
        click[1] += Math.Max(near, N) - Math.Min(near, N);
        click[2] += Math.Max(up, N) - Math.Min(up, N);
        click[3] += Math.Max(down, N) - Math.Min(down, N);
        click[4] += Math.Max(large, N) - Math.Min(large, N);
        click[5] += Math.Max(small, N) - Math.Min(small, N);

        Console.WriteLine(Math.Min(Math.Min(Math.Min(click[0], click[1]), Math.Min(click[2], click[3])), Math.Min(click[4], click[5])));
    }
}

반례는 다 맞았는데 결과는 틀렸습니다.

뭐가 틀린 건지 진짜 모르겠다.

경우의 수에서 놓친 부분이 있나본데 뭘까...