[BOJ/백준][Gold4] 1437 : 수 분해 (C++)

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

1437번: 수 분해

 

[난이도] Gold4
[유형] Greedy

[풀이]
3이 최대만 많이 되도록
3^k , 3^k*2, 3^k*4 의 형태로 만들어 주면 가장 큰 수를 만들 수 있습니다.
즉 3으로 나눴을 때 나머지가 1이면  3^k*4의 형태로, 나머지가 2이면 3^k*2로 만들어 주면 됩니다.

예제5번의 답이 3^k * 4의 형태라 여기서 힌트를 얻었지만 수학적으로 왜 그렇게 되는지는 분석이 필요할 것 같습니다.

 

 

#include <cstdio>
using namespace std;
int N,mod=10007;
int main(){
    scanf("%d",&N);
    if(N==0){
        puts("0");
        return 0;
    }

    int k = N/3;
    int m = N%3;
    int ret=1;
    if(m==1) {
        if(k>0) {
            k--;
            ret=4;
        }
    }else if(m==2){
        ret=2;
    }

    for(int i=0;i<k;i++) ret=(ret*3)%mod;
    printf("%d",ret); 
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/1437.cpp