1094번. 막대기

phoenixKim·2022년 8월 28일
0

백준 알고리즘

목록 보기
90/174

문제 잘못됨.

-> 위에서 자른 막대의 절반을 바로 버리는 것이 아님, 제외하고라는 표현이 어울림.
: 질문 게시판에도 수정요청 있음.


풀이전략

1) 벡터 컨테이너에 64를 집어 넣고 시작

2) back에 있는 것을 뽑아서 반절로 만듬.

3) 벡터의 모든 원소를 더한 다음에 2번에서 구한거랑 뺌

4) n과 비교를 해서

5 - 1) 작다면 back에 있는거를 반절로 만들고, 2번의 막대기를 추가함.
5 - 2) 크다면? back에 있는거를 반절로 만듬.

코드


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


// 23:14 ~ 23:43
int main() 
{
	//64 -> 23으로 만들어야 함.
	//횟수를 구하라. 

	// 64 
	// vs 48 
	// 64 -> 32 32
	// 32 16 16 -> 16제외하고 32 + 16 더함 -> 48 총 2개의 막대.

	//64 
	// vs23 
	// 32 32 -> 32버림 카운트 1
	// 16 16 -> 16하나 제외하고 16 vs 23 작으므로 안버림 , 카운트 2
	// 16 8 8 -> 8하나 제외하고 , 24 vs 23 크므로 8버림, 카운트 3
	// 16 4 4 -> 4하나 제외하고 20 vs  23 작으므로 안버림., 
	// 16 4 2 2 -> 2하나 제외하고, 22 vs 23 작으므로 안버림.
	// 16 4 2 1 1 -> 1하나 제외하고, 23 vs 23 동일하므로 1을 버림.
	// => 남은 막대는 총 16 4 2 1 //4개임.


	int n;
	cin >> n;
	
	vector<int>v(1, 64);
	int stick = 64;
	int cnt = 1;

	if (n == 64)
	{
		cout << v.size() << endl;
		return 0;
	}

	while (1)
	{
		// 길이가 가장 짧은 것을 반으로 자름.
		int half = v.back() / 2;
	
		int temp = 0;
		for (int i = 0; i < v.size(); ++i)
		{
			temp += v[i];
		}
		temp -= half;
	
		if (temp >= n)
		{
			//마지막 인덱스의 원소를 반절로 해야 함. 
			v[v.size() - 1] -= half;
		}
		//오히려 막대기 추가함.
		else
		{
			v[v.size() - 1] -= half;
			v.push_back(half);
		}
		
		if (temp == n)
		{
			cout << v.size() << endl;
			return 0;
		}
	
		//남아 있는 막대기의 합이 
	
	
	}



 }

profile
🔥🔥🔥

0개의 댓글

관련 채용 정보