[BOJ] 20548 칠리소스

(2021년 1월 16일에 작성한 글입니다.)

 

20548번: 칠리소스

 

문제를 정리하면

가능한 칠리 소스의 맵기를 오름차순으로 나열 한 후

앞에서부터 1단계부터 차례로 번호를 매길 때

내가 고른 소스는 몇 단계인가? 이다.

​

처음에 메모리 초과로 틀렸는데

int 형을 사용해서 오버플로우가 나와 while문이 계속 돌아서 그랬다.

long long으로 바꾸니까 맞았다.

​

chilli 라는 벡터를 만들어줘서 처음에 0을 넣고

n은 1부터 시작해서 매번 7배가 된다.

그리고 기존에 있던 값들에 n * 1을 더해서 벡터에 넣고,

n * 2를 더해서 또 벡터에 넣는다.

이 과정을 끝내고 벡터 안에 찾고자 하는 값이 있는지 확인한다.

만약 있다면 반복문을 종료하고 lower_bound를 이용해서 인덱스 번호를 출력하면 된다.

없다면 있을때까지 반복하면 되고.

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll input;
	ll cnt;
	ll n = 1;

	cin >> input;

	vector<ll> chilli;
	chilli.push_back(0);

	for (ll n = 1; ; n *= 7) {
		ll size = chilli.size();
		for (ll i = 0; i < size; i++) {
			chilli.push_back(chilli[i] + n);
		}
		for (ll i = 0; i < size; i++) {
			chilli.push_back(chilli[i] + n * 2);
		}

		if (binary_search(chilli.begin(), chilli.end(), input)) {
			cout << lower_bound(chilli.begin(), chilli.end(), input) - chilli.begin();
			break;
		}
	}

	return 0;
}