[C/C++] 백준 1437번 - 수 분해

문제

음이 아닌 정수 N을 한 개 이상의 음이 아닌 정수의 합으로 나타낼 때, 이를 "N을 분해한다"라고 부르자.

예를 들어, 4 = 1+1+1+1 = 1+1+2 = 1+3 = 2+2 = 4 로 나눌 수 있다.

분해 곱이란 N을 분해해서 나타난 수들을 전부 곱한 것을 의미한다. N=4일 때, 분해 곱은 다음과 같다.

• 4 = 1+1+1+1, 곱 : 1×1×1×1 = 1
• 4 = 1+1+2, 곱 : 1×1×2 = 2
• 4 = 1+3, 곱 : 1×3 = 3
• 4 = 2+2, 곱 : 2×2 = 4
• 4 = 4, 곱 : 4

N이 주어졌을 때, 그 수의 분해 곱의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 음이 아닌 정수 N이 주어진다. N은 1,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 수의 분해 곱의 최댓값을 10,007로 나눈 나머지를 출력한다.

예제 입력 1

7

예제 출력 1

12

 

 

<코드>

#include<iostream>
#include<algorithm>
using namespace std;
	
int N;
long long ans;
	
int main()
{

	cin >> N;
	ans = 1;
	
	while(N >= 5)
	{
		ans = (3*ans)%10007;
		N-=3;
	}
	cout << (ans*N)%10007 << endl; 
}

 

풀이 방법

만들 수 있는 분해곱 중에서 3을 최대한 넣는 것이 풀이 포인트입니다.

(대신 N이 5 미만일 때는 N 그자체 값이 분해곱의 최대값.)

 

 

www.acmicpc.net/problem/1437

1437번: 수 분해