[1094] 막대기

https://www.acmicpc.net/problem/1094

1094번: 막대기

 

---

 

 해결 방법 

이 문제는 사실 문제 설명에서 알고리즘이 다 주어진다. 그냥 진짜 적혀있는대로 코드를 작성하면 된다.

막대의 길이를 저장할 벡터를 선언한 후(배열명 : stick), 초기값인 64를 집어넣는다.

while문을 돌면서 매번 현재 가지고 있는 막대 중 가장 짧은 것,

즉, 벡터의 가장 마지막 원소를 2등분 해서 다시 벡터에 넣어주고 문제의 과정을 반복하면 된다. 

전체 과정을 그림으로 보면 아래와 같다

  

내가 얻고자 하는 길이가 64인 경우, 막대 한 개만 필요하기 때문에

이때는 while문을 돌게 하지 않고 answer을 1로 초기화 해준다음

while문에서 return 되지 못한다면 함수의 마지막 부분에서 answer을 출력하도록 작성하였다!

 

---

 

 내 코드(C++) 

// [1094] 막대기
// https://www.acmicpc.net/problem/1094

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	int x, answer = 1;
	vector<int> stick; // 현재 가지고 있는 막대들의 길이
	stick.push_back(64);
	cin >> x;
    
	while (stick[stick.size() - 1] != 1) {
		int temp = stick[stick.size() - 1] / 2;
		int sum = 0;
		stick.pop_back();
		stick.push_back(temp); stick.push_back(temp); // 가장 짧은 막대를 절반으로 자름
		
        for (int i = 0; i < stick.size(); i++) {
			sum += stick[i];
		}
        
		// 위에서 자른 막대의 절반 중 하나를 버리고 남아있는 막대의 길이의 합이 x보다 크거나 같다면
		if (sum - stick[stick.size() - 1] >= x) {
        
			// 남아있는 막대 길이의 합이 내가 얻고자 하는 길이인 경우
			if ((sum - stick[stick.size() - 1]) == x) {
				answer = stick.size() - 1;
				cout << answer;
				return 0;
			}
            
			stick.pop_back(); // 젤 마지막 막대기(위에서 자른 절반 중 하나) 제거
		}
	}
	cout << answer;
}