BOJ 19134 - $2x + 2$

BOJ 19134 - $2x + 2$

일단 bigint 를 써주면 된다.

이 문제가 그리디하게 $1$부터 $(n-2)/2$ 가 선택되어있는지 검사하다보면 특정한 규칙이 보이는데, 그 규칙을 이용하기가 어렵다.

$16n-2$ 의 수들이 바로 딱 적용할 수 있는것이 아닌 규칙이 나오기 때문이다.

거기에 생각이 매몰되어서 오래헤맸다.

풀이는 단순한데, $n$ 부터 본다고 하자.

$n$이 홀수라면 항상 포함시켜준다. $2x+2$가 홀수가 나올 일이 없기 때문이다.

그렇지 않다면 $n$은 짝수이다.

그럼 $n/2 \sim n$ 까지의 수들 $n/2+1$ 개를 집합에 넣어준다.

일단 최대한 많이 집어 쳐넣는것으로 그리디를 성립시킬 수 있다.
왜냐하면 어차피 각 수들이 가지는 $2x+2$와 $\dfrac {x-2}2$ 는 항상 쌍을 이루기 때문에 포함될 수 있는것을 먼저 넣어버리는게 이득이다.

그러면 집합에서 가장 작은 수는 $n/2$ 가 되었고, $2x+2<n/2$ 가 되는 가장 큰 $x$를 잘 구해서 그 다음 재귀함수의 인자로 넘겨준다.

이렇게 그리디하게 포함시켜주기만 하면 풀 수 있다.

bigint fn(bigint n) {  
   if (n < 0) return 0;  
   if (n < 4) return n;  
   if (n % 2 == 1) return bigint(1) + fn(n - 1);  
  
   bigint ret = n / 2 + 1;  
   bigint nxt = n % 4 == 0 ? n / 4 - 2 : n / 4 - 1;  
  
   return ret + fn(nxt);  
}  
  
void solve() {  
   bigint n;  
   cin >> n;  
   cout << fn(n);  
}