백준 31926 밤양갱 (c++) : 피너클

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

일단 daldidalgo를 만드는데

d

da

dal

dald

daldi

daldidal

daldidalg

daldidalgo

총 8의 시간이 걸린다.

그리고 daldidan을 만들때는 무조건 앞에 daldidalgo이 있는 경우이기 때문에 

daldidalgo에서 daldida를 가져와서

daldida

daldidan

총 2의 시간이 걸린다.

 

n = 1의 경우

daldidalgo를 만드는데 8

daldidan을 만드는데 2 총 10의 시간이 걸린다.

 

n = 2의 경우에는

daldidalgo를 만드는데 8

daldidalgo를 앞에서 복사해서 1

daldidan을 만드는데 2 총 11의 시간이 걸린다.

 

그런데 n = 3의 경우

daldidalgo을 만드는데 8

daldidalgo를 앞에서 복사해서 1

이러면 지금까지

daldidalgodaldidalgo 가 만들어진거고 이제 우리는

daldidalgodaldidan 을 만들어야 한다. 이제 보면 보인다.

daldidalgodaldidalgo에서 daldidalgodaldida를 가져오고 n만 추가하면 끝이다. 총 2의 시간이 걸린다.

그래서 n = 3의 경우 총 11의 시간이 걸린다.

 

n = 4의 경우

daldidalgo을 만드는데 8

daldidalgo를 앞에서 복사해서 1

지금까지 daldidalgodaldidalgo가 만들어졌고 daldidalgodaldidalgo를 그대로 복사해

daldidalgodaldidalgodaldidalgodaldidalgo를 만드는데 1

그후엔 daldidalgodaldidan를 만드는데 2

그래서 n = 4의 경우 총 12의 시간이 걸린다.

 

n = 5의 경우 계산하면 12의 시간이 걸리고

n = 8의 경우 계산하면 13의 시간이 걸린다.

 

이제 규칙이 보인다.

n = 2 -> 11시간

n = 3 -> 11시간

n = 4 -> 12시간

n = 5 -> 12시간

...

n = 8 -> 13시간

n이 2의 배수가 될때마다 1의 시간이 증가한다.

int add = 1;
int num = 0;
while (add <= n / 2) {
	add *= 2;
	num++;
}

n이 7일 경우 n / 2는 3이다.

add = 1이니 2를 곱하면 add = 2가 되고 num은 1이 더해지니 1이 된다.

add = 2이니 2를 곱하면 add = 4가 되고 num은 1이 더해지니 2이 된다. 이러면 반복문이 끝난다.

 

n이 8일 경우 n / 2는 4이니 add가 8일때 반복문에서 나와지고 num은 3이된다.

n이 9일 경우 n / 2는 4이니 add가 8일때 반복문에서 나와지고 num은 3이 된다.

n이 15일 경우 n/2는 7이니 add가 8일때 반복문에서 나와지고 num은 3이 된다.

n이 2의 배수일 경우에만 1이 더해지는걸 볼수있다.

cout << 8 + num + 2 << endl;

이제 기본적으로 들어가는 시간인 10에다가 num을 더하면 된다.

#include <iostream>

using namespace std;

int n;

int main()
{
	cin >> n;

	int add = 1;
	int num = 0;
	while (add <= n / 2) {
		add *= 2;
		num++;
	}
	cout << 8 + num + 2 << endl;
}

전체코드다.