글 읽기 - 반례 부탁드립니다...

(追記) (追記ここまで)

반례 부탁드립니다...

1107번 - 리모컨

rhy123123 1년 전 0

제가 생각할 수 있는 모든 경우는 포함했다고 생각했는데, 계속 15%에서 오답처리 됩니다.
n이 최대 500000이므로 int형 오버플로우도 아닐테고.. 감이 안잡히네요

(앞에 DEBUG 처리한 코드들은 무시하셔도 됩니다.)

52 : n=100일 때, 이미 목표 채널이므로 0
59: 목표 채널에 고장난 키가 없으므로 그대로 입력하면 끝, 자리수가 정답
66: 모든 키가 고장, 100에서 출발해야 함

73~: 일반적인 케이스
76: 목표 채널부터 위로, 아래로 동시에 뻗어나가서 고장난 키를 포함하지 않는 채널까지 도달
82: 아래로 가서 음수에 도달하면 위로 가는 것이 정답이므로 그에 대한 처리
92: 목표 채널부터 이동한 거리가 100에서 이동하는 것보다 클 경우 후자를 정답으로 함
101, 107: 정답 방향에 따른 처리

-- 이후 다른 질문들에서 찾은 반례 --

- lower, higher중에 100이 발생하는 경우 정답보다 3 큰 값이 출력됨(해결 / 15%)
- 고장난 키가 없지만, 100에서 접근하는 것이 더 빠른 경우(해결 / 15%)

- 다음 예제에 대한 출력이 잘못됨 (https://www.acmicpc.net/board/... line 24) (해결 / 35%)
[contain 함수에 number = 0이 들어갈 때의 예외처리, 99줄 100에서 갈 때와 비교시에 등호 추가]
(해당 게시글의 반례 전부 해결했습니다. 여전히 35%)
0
2
0 1

#include <iostream>
using namespace std;
#define DEBUG if(1)
/** return 1 if 'number' contain any digit in arr 'd' */
int contain(int number, int* d) {
 if(number == 0) {
 for(int* i = d ; *i != -1 ; i++)
 if(0 == *i) return 1;
 return 0;
 }
 while(number) {
 for(int* i = d ; *i != -1 ; i++)
 if(number%10 == *i) return 1;
 number /= 10;
 }
 return 0;
}
/** return how much digits 'number' have */
int digit(int number) {
 if(number == 0) return 1;
 int d=0;
 while(number) {
 d++;
 number /= 10;
 }
 return d;
}
int main()
{
 int n, m, broken[11];
 cin >> n >> m;
 for(int i=0 ; i<m ; i++)
 cin >> broken[i];
 broken[m] = -1; // endpoint : -1
 DEBUG {
 cout << endl << n << " [ ";
 for(auto i : broken) {
 if(i == -1) break;
 cout << i << ' ';
 }
 cout << ']' << endl;
 }
 // 100
 if( n==100 ) {
 DEBUG cout << "이미 목표에 있음" << endl;
 cout << 0 << endl;
 return 0;
 }
 // No broken
 if( !contain(n, broken) ) {
 DEBUG cout << "부서진 키 포함X, 자리수[[또는 100에서 접근]]가 정답" << endl;
 int ans = min( digit(n), abs(n - 100) );
 cout << ans << endl;
 return 0;
 }
 // All broken
 if( m==10 ) {
 DEBUG cout << "가능한 숫자키가 없으므로 100에서 가야 함" << endl;
 cout << abs(n - 100) << endl;
 return 0;
 }
 // normal case
 int lower=n, higher=n;
 int count=0;
 while( lower>=0 && contain(lower, broken) && contain(higher, broken) ) {
 lower--, higher++;
 count++;
 }
 if( lower<0 ) {
 // lower is invalid. consider higher only.
 while(contain(higher, broken))
 higher++, count++;
 DEBUG cout << "Lower invalid. Higher:" << higher << ", count:" << count << endl;
 cout << digit(higher) + count << endl;
 return 0;
 }
 if( count >= abs(n - 100) ) {
 DEBUG cout << "100에서 가는게 더 빠름" << endl;
 cout << abs(n - 100) << endl;
 return 0;
 }
 DEBUG cout << "Low : " << lower << (contain(lower , broken) ? " (X)" : "") << endl
 << "High : " << higher << (contain(higher, broken) ? " (X)" : "") << endl
 << "Count: " << count << endl;
 if( !contain(lower, broken) ) {
 DEBUG cout << lower << '+' << count << endl;
 cout << digit(lower) + count << endl;
 return 0;
 }
 if( !contain(higher, broken) ) {
 DEBUG cout << higher << '-' << count << endl;
 cout << digit(higher) + count << endl;
 return 0;
 }
 return 0;
}

srand 1년 전 1

In #1:
217
8
0 1 2 4 5 6 7 9
Out #1 :
119
Ans #1 : 
117 (100 번 채널에서 117번 + 눌러 217로 이동)

In #2 :
97
6
1 3 5 6 7 8
Out #2 :
4
Ans #2 :
3 ( 100 번 채널에서 3번 - 눌러 97로 이동)

출력 하는 곳 조건들을 보면,

if ( ... ) print

if ( ... ) print

이러한 형태인데,

if ( ... ) ans = min ( ans, ... )

if ( ... ) ans = min ( ans, ... )

print ans

최종적으로 한번 출력하면 조건에 따른 오류를 줄일 수 있을 것 같아요

rhy123123 1년 전 0

제공해주신 반례들 덕분에 해결했습니다! 출력하는 방식 때문은 아니었고, 제가 생각하지 못한 edge case가 더 있었던 거였네요

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)