글 읽기 - 게시판 반례 정독했는데도 반례를 못 찾겠습니다ㅜㅠ 고수분들 부탁드려요

coding_jun 2년 전 0

목표 채널을 n번이라고 하면

1. 남아있는 버튼으로 누를 수 있는 n보다 작은 채널 중 가장 큰 채널 번호와 100과의 차이 + 그 채널 번호의 길이

2. 남아있는 버튼으로 누를 수 있는 n보다 큰 채널 중 가장 작은 채널 번호와 100과의 차이 + 그 채널 번호의 길이

3. n과 100의 차이

4. n번의 자릿수

이 4가지 중 가장 작은 값을 출력하도록 코드를 짰습니다.

mini는 남아있는 버튼으로 누를 수 있는 n보다 작은 채널 중 가장 큰 채널 번호를 출력하는 함수입니다.

nt는 False가 되면 이미 만들어지는 숫자가 n보다 작아졌음을 의미합니다.

nodab은 False가 되면 이미 자릿수가 작아져야만 n보다 작은 숫자를 만들 수 있음을 의미합니다.

n이 k+1자리 숫자이면 남아있는 버튼의 최솟값이 10^(k-1)자리의 숫자보다 큰 지 작은 지를 확인하여 10^k 자리의 숫자를 결정하는 방식으로 코드를 구성했습니다.

maxi는 남아있는 버튼으로 누를 수 있는 n보다 큰 채널 중 가장 작은 채널 번호를 출력하는 함수입니다.

mt는 False가 되면 이미 만들어지는 숫자가 n보다 커졌음을 의미합니다.

n n이 k+1자리 숫자이면 남아있는 버튼의 최댓값이 10^(k-1)자리의 숫자보다 큰 지 작은 지를 확인하여 10^k 자리의 숫자를 결정하는 방식으로 코드를 구성했습니다.

게시판 정독해봤는데도 반례가 안 나와서 어디서 틀린건지 못 찾겠습니다.

고수분들 반례 찾아주시면 정말 감사하겠습니다.

import sys
input = sys.stdin.readline
n = input().rstrip() # 목표 채널의 str값
d = int(input()) # 고장난 버튼의 개수
def mini(num1, n): # 남아있는 버튼으로 누를 수 있는 n보다 작은 채널 중 가장 큰 채널의 str값
    nt = True # 채널값이 이미 n보다 작아졌는지 확인하기 위한 값
    nodab = True # False가 되면 n보다 자리수가 작아져야만 n보다 작은 채널을 누를 수 있음을 의미
    mn = '' # 채널값
    for i in range(len(n) - 1):
       if nodab:
            if nt:
                if u <= int(n[i + 1]):
                    if int(n[i]) in num1:
                        mn += n[i]
                    else:
                        c = 0
                        for j in num1:
                            if j < int(n[i]):
                                mn += str(j)
                                nt = False
                                break
                            c += 1
                        if c == N:
                            nt = False
                            nodab = False
                else:
                    if u < int(n[i]):
                        for l in num1:
                            if l < int(n[i]):
                                mn += str(l)
                                nt = False
                                break
                    else:
                        nt = False
                        nodab = False
            else:
                mn += str(v)
       else:
            mn = str(v) * (len(n)-2)
            break

    if nt:
        for i in num1:
            if i <= int(n[len(n) - 1]):
                mn += str(i)
                break
    else:
        mn += str(v)
    if mn == '':
        mn = '9999999'
    return mn

def maxi(num2, n): #남아있는 버튼으로 누를 수 있는 n보다 큰 채널 중 가장 작은 채널의 str값
    mt = True # 채널값이 이미 n보다 커졌는지 확인하기 위한 값
    mx = '' # 채널값
    if v < int(n[0]):
        mt = False
        if u != 0:
            mx += str(u)
        else:
            if len(num2) >= 2:
                mx += str(num2[1])
            else:
                mx += str(u)
    for i in range(len(n) - 1):
        if mt:
            if v >= int(n[i + 1]):
                if int(n[i]) in num2:
                    mx += n[i]
                else:
                    c = 0
                    for j in num2:
                        c += 1
                        if j > int(n[i]):
                            mx += str(j)
                            mt = False
                            break
            else:
                if v > int(n[i]):
                    for l in num2:
                        if l > int(n[i]):
                            mx += str(l)
                            mt = False
                            break
        else:
            mx += str(u)
    if mt:
        for i in num2:
            if i >= int(n[len(n) - 1]):
                mx += str(i)
                break
    else:
        mx += str(u)
    if int(mx) == 0:
        mx = '9999999'
    return mx
if d != 0: # 고장난 버튼이 1개 이상일 때
    delete = list(map(int, input().split()))
    num1 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
    num2 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in delete:
        num1.remove(i)
        num2.remove(i)
    N = len(num1)
    if d != 10: # 고장난 버튼이 1개 이상 10개 미만일 때
        u = min(num1)
        v = max(num1)
        print(min(abs(int(n) - int(mini(num1, n))) + len(mini(num1, n)),
                  abs(int(maxi(num2, n)) - int(n)) + len(maxi(num2, n)), abs(int(n) - 100)))
    else: # 고장난 버튼이 10개일 때
        print(abs(int(n)-100))
else: # 고장난 버튼이 0개일 때
    print(min(abs(int(n)-100), len(n)))

ahmg1216 2년 전 0

애초에 출력값이 이상합니다 왜 세개를 다 출력하시죠

ahmg1216 2년 전 0

또한 구해야 할 최소는 100번으로 가는 최소가아닌 n으로 가는 최소이고 기본값이 100번입니다

coding_jun 2년 전 0

세 개 중 최솟값을 출력하도록 min으로 설정했습니다!

djm03178 2년 전 4

랜덤으로 찾은 반례입니다.

139133
7
9 6 8 2 1 5 7
output: 94695
correct answer: 94694

djm03178 2년 전 3

더 작은 반례입니다.

14
2
1 5
output: 7
correct answer: 6

coding_jun 2년 전 0

아 감사합니다. mini에서 n보다 작은 숫자 중 만들 수 있는 최댓값 출력할 때 앞에 0이 붙어있었네요

ahmg1216 2년 전 0

죄송합니다 복붙하다 뭔가 잘못 되었나 보네요

coding_jun 2년 전 0

아니에요~

coding_jun 2년 전 0

이제는 ValueError가 뜨네요,,,ㅎㅎㅎ

ahmg1216 2년 전 2

35386

9 7 8 6 5 4 1 0 2

ahmg1216 2년 전 2

반례입니다

coding_jun 2년 전 1

감사합니다. 덕분에 런타임에러 해결해서 맞았네요.

min413 1년 전 0

9 7 8 6 5 4 1 0 2

이렇게 정렬 안 된 상태로 입력될 수 있다는 걸 알고 나서 해결했습니다.

진심으로 감사합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

게시판 반례 정독했는데도 반례를 못 찾겠습니다ㅜㅠ 고수분들 부탁드려요

coding_jun 2년 전 0

ahmg1216 2년 전 0

ahmg1216 2년 전 0

coding_jun 2년 전 0

djm03178 2년 전 4

djm03178 2년 전 3

coding_jun 2년 전 0

ahmg1216 2년 전 0

coding_jun 2년 전 0

coding_jun 2년 전 0

ahmg1216 2년 전 2

ahmg1216 2년 전 2

coding_jun 2년 전 1

min413 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말