[BOJ][C++] 백준 1094번 막대기
Updated:
1094번 막대기
1. 문제 정보
백준 온라인 저지 [1094번 막대기] 문제의 링크입니다.
문제
지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대를 만들려고 한다.
막대를 자르는 가장 쉬운 방법은 절반으로 자르는 것이다. 지민이는 아래와 같은 과정을 거쳐서 막대를 자르려고 한다.
- 지민이가 가지고 있는 막대의 길이를 모두 더한다. 처음에는 64cm 막대 하나만 가지고 있다. 이때, 합이 X보다 크다면, 아래와 같은 과정을 반복한다.
- 가지고 있는 막대 중 길이가 가장 짧은 것을 절반으로 자른다.
- 만약, 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의
합이 X보다 크거나 같다면, 위에서 자른 막대의 절반 중 하나를 버린다.- 이제, 남아있는 모든 막대를 풀로 붙여서 Xcm를 만든다.
X가 주어졌을 때, 위의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 X가 주어진다. X는 64보다 작거나 같은 자연수이다.
출력
문제의 과정을 거친다면, 몇 개의 막대를 풀로 붙여서 Xcm를 만들 수 있는지 출력한다.
예제 입력1
23
예제 출력1
4
예제 입력2
32
예제 출력2
1
예제 입력3
64
예제 출력3
1
예제 입력4
48
예제 출력4
2
시간 / 메모리 제한
2초 / 128MB
2. 생각
-
문제에서 주어진 알고리즘을 그래도 따라가면 되는 문제였습니다. 막대기의 길이를 나타낼 변수 stick과 막대기의 개수를 나타앨 cnt 변수, 그리고 우리가 최종적으로 만들어내야할 수 x를 가지고 알고리즘을 따라갑니다.
-
막대기가 우리가 만들려고 하는 수보다 작거나 같다면 막대기가 하나 이상 필요할 것입니다. 그래서 막대기의 개수를 1 증가시켜주고 우리가 만들려고 하는 수에서 막대기 길이를 뺍니다. 그리고 이 과정을 x가 0이 될 때까지 반복한다면 cnt에는 최종적으로 막대기의 개수가 남게 됩니다.
3. 소스코드 (C++)
