백준 1437 - 수 분해

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

 

아마 이 글에 들어왔으면 같은 생각을 하고 있었을지도 모른다.

 

"2 끼리 빼고 남는 거 3 만드는 게 최적해 아닌가?"

 

놀랍게도 아니다. 3씩 빼서 세제곱을 먹이는 게 더 커진다.

 

조금만 생각해도 제곱 증가량 < 세제곱 증가량인걸 눈치챌 수 있다. 아뿔싸!

 

따라서 3씩 빼다가 나머지가 1이면 하나를 4로 만들고, 나머지가 2면 2를 하나 만들어주는 식으로 전개한 뒤에 계산하면 최적해가 된다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n;
const int mod = 10007;
 
void solve() {
  cin >> n;
 
  if (n <= 3) {
    cout << n;
    return;
  }
 
  int cnt = n / 3;
  ll ans = 1;
  if (n % 3 == 2) ans = 2;
  else if (n % 3 == 1) --cnt, ans = 4;
 
  while (cnt--) {
    ans *= 3;
    ans %= mod;
  }
  cout << ans;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록