[C++] 백준 1094번 풀이 (막대기)

정민경·2023년 2월 7일
0

baekjoon

목록 보기
29/57
post-thumbnail

- 문제 (1094번) : 막대기

  • 64 cm의 막대기를 절반으로 잘라 붙여서 입력받은 X cm의 막대기를 만들 때 몇 개의 막대가 필요한지 구하는 문제

- 입력 및 출력

[ 입력 ]

  • 첫째 줄에 만들 막대기의 길이 X 입력
    ( X ≤ 64, 자연수 )

[ 출력 ]

  • 필요한 막대기의 수 출력

- 문제 풀이

  • 이 문제의 중요 point는 처음 가지고 있는 막대기가 64cm이고, 절반으로 나눈다는 것이다.

  • 막대기를 절반으로만 나눠 사용 가능하므로, 사용할 수 있는 막대기의 길이는

    1 2 4 8 16 32 64

    이렇게 7가지만 사용 가능하다.
    수를 이진수로 생각할 수 있다면 매우 간단하게 해결된다.

  • 내가 만들 수 X를 이진수로 변환한 후 1의 개수를 구하면 그 값이 X cm 의 막대기를 만들 때 필요한 막대기의 개수가 된다.

    < ex >

    • 64 cm -> 0100 0000 이므로 1개
    • 33 cm -> 0010 0001 이므로 2개
  • 따라서 이 문제는 입력받은 X를 이진수로 변환해 1의 개수를 출력하면 해결된다.


- 최종 코드

0개의 댓글