joo9327   11달 전

지민이는 길이가 64cm인 막대를 가지고 있다. 어느날 갑자기 지민이는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 막대를 몇 개의 작은 막대로 자른다음, 합쳐서 Xcm를 만드려고 한다.
지민이가 막대를 자르는 방법은 다음과 같다.


1) 모든 막대의 길이를 더한다. (처음에는 64cm이다) 이 값이 X보다 크다면, 아래와 같이 한다.

  1.길이가 가장 짧은 막대를 골라서 반으로 자른다.
  2.위에서 자른 막대 중 하나와 나머지 막대 길이의 합이 X보다 작지 않다면, 자른 막대 중 하나를 버린다.

2) 남은 막대를 붙여서 Xcm를 만든다.


문제가 이런식인데 x=23이라고 치고처음에 64 이니깐

1-1에 의해서 64 -> 32 32 이렇게 두개가 나오고

1-2에 의해서 자른막대(32)와 나머지 막대(현재 없음)길이가 x보다 작지 않다면 하나를 버린다고 했으니

32 32 두개중 하나를 버리게 되면

현재 가지고 있는 막대는 32 한개뿐이지 않나요?


그럼 위에 그대로 반복되다보면 32 -> 16 16

16버림

16 에서 더이상 더하거나 그럴게 없는데 문제가 이상한건가요 제가 이해를 못하는 건가요?

handrake   11달 전

64 -> 32 32 (32 버림) since 32 + 32 > 23

32 -> 16 16 since 16 + 16 > 23

16 -> 16 8 8 (8 버림) since 16 + 8 > 23

8 -> 16 4 4 since 16 + 4 < 23, 4 놔둠

4 -> 16 4 2 2

2 -> 16 4 2 1 1

16 + 4 + 2 + 1 = 23


감사합니다.

baekjoon   11달 전

문제 설명을 수정해봤습니다.

ficnfhii   7달 전

..저도 질문쓰신분처럼 이해했는데, 답글달아주신분의 해설보니 더 이해가 안가네요 ;;

답글달아주신분 2번째 줄에 32 -> 16 16 since 16 + 16 > 23  이 부분 보면, 


16 + 16이 32니까 1-2의 설명처럼 막대 길이의 합이 X(=23)보다 작지 않다면, 자른 막대 중 하나자인  16을 버리고

그런 후,  3번째 줄에는  16 -> 8 8  로 시작되어야 하지 않나요 ? 

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