Rose   5년 전

문제풀다 너무 고통스러워서 다른분들 고통받지 말라고 수작업으로 진행했습니다. 

많은 도움 되길 바랍니다.

@gkfkagkfka12

hsunj2003   5년 전

이게 전부 돌아가도 틀리다면 대체 뭐가 문제일까요 ㅠㅠ

startlink   5년 전

재채점했습니다.

sanha93   4년 전

하 너무 고통스러웠네요;; 정말 감사합니다... 차라리 -1, +1 해가며 되는 수 찾는게 더 빨랐을 지도 모른다는 생각이 문득 드네요; 잘봤습니다.

ham3798   4년 전

다 넣어도 맞는데 틀렸다네요 ㅎㅎ

niklasjang   4년 전

추가 예외입니다!

5

2

4 6

답 : 1

정리해주신 예외에는 "제외한 숫자들 사이에 목적지가 있는 경우"를 커버하는 TC가 없었습니다.

niklasjang   4년 전

제가 정리한 경우의 수 입니다.

broken : 고장난 버튼의 수

dst(s) : s 에서 목적지까지 +1 또는 -1로만 이동했을 때 최소 거리

digit(i) : i까지 가기 위해서 누르는 버튼의 수

-------------------------------------------

- broken이 0일 때 :dst(100)와 digit 중 작은 값이 답

- broken이 10일 때 : dst(100)가 답

- broken이 9이고 0번 버튼만 쓸 수 있는 경우 :  dst(100)와 '0으로 이동한 뒤 dst(0)'의 최소 

- 고장나지 않은 버튼 중 제일 작은 수의 버튼이 목적지보다 큰 경우

- 고장나지 않은 버튼 중 제일 작은 수의 버튼이 목적지보다 작은 경우

niklasjang   4년 전

위 처럼 모든 경우를 따져보지 않고 구하는 방법입니다. 

본래 이것이 더 부르트포스 접근 방식에 더 부합하는 것 같습니다.

네이버에 백준1107로 검색하면 제일 위에 나오는 블로그에서는 아래와 같이 설명했습니다.

고장나지 않은 모든 버튼들을 조합해서 누르는 모든 경우에 대해서 

(버튼을 누르는 수) + (버튼을 누른 뒤 목적지까지 +1/-1로 이동할 때 최소 거리)를 모두 구하고 이들의 최소값을 구한다.

tough002   3년 전

이 문제 반례 찾는데 한참 걸렸네요. 저같은 경우 두가지 오류가 있었습니다. 

1. 불량인 버튼이 순서대로 온다고 가정하는 오류 : 불량 버튼 리스트는 순서와 상관없이 주어질수 있습니다. 

2. 버튼 입력수 + abs(입력 필요값 - 입력 가능값) 전체에 대한 min값을 업데이트 해야 하는데 뒷항에 대해서만 min을 업데이트 하고 나중에 버튼 입력수를 더하는 오류

반례 찾는데 도움이 되셨으면 하는 마음에 글 올립니다. 

qorgkr26   2년 전

1555
8
0 1 3 4 5 6 7 9


답:670


이 예제 왜 답이 671이 아니라 670인가요? 고수님들의 설명 부탁드립니다..

baha1909   2년 전

1555

8 0 1 3 4 5 6 7 9

답:670



2222 에서 접근하시지 마시고 888에서 접근하시면 670이 나옵니다

ganzang_dady   2년 전

@niklasjang 와.. 진짜 뽀뽀해드리고 싶다

kmy17518   2년 전

위에 테스트케이스 다 통과했는데도 답 틀려서 코드 다시 살펴봤더니

가장 가까운 수가 자릿수가 하나 늘어나고, 가능한 버튼이 한개일 때 처리를 잘못하고 있었네요

테스트케이스 첨부합니다!

889

9

0 2 3 4 5 6 7 8 9

답: 226

ghddhksduq   1년 전

감사합니다~~~~

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