[백준/BOJ] 1437. 수 분해 [Gold 4]

1437. 수 분해

문제출처 : https://www.acmicpc.net/problem/1437

code

#include <iostream>
using namespace std;

int dp;

int main()
{
	int N, cnt = 0;
	cin >> N;

	if (N > 4)
	{
		cnt = N / 3;
		N = N % 3;
		if (N % 3 <= 1)
		{
			cnt--;
			N += 3;
		}

		for (int i = 0; i < cnt; i++)
		{
			dp = N * 3 % 10007;
			N = dp;
		}
		cout << dp;
	}
	else
		cout << N;

	return 0;
}

오늘 교양시험 3개치고 기분이 좋아서 오랜만에 백준을 풀었다.

아직 전공시험3개 교양시험2개가 남았지만... 오늘만 쉬자..!

처음에 수를 어떻게 분해해야 최댓값이 나올까 고민해봤는데, 다른 블로그에서 최대한 3이 많이 들어가게끔 분해를 해야 분해 곱이 최댓값이나온다고하더라.

수를 분해하는데 까지는 별로 어렵진 않은데, 출력조건에 분해 곱의 최댓값을 10007로 나눈 나머지를 출력하라고 되어있는데, 분해 곱을 모두 구한다음 마지막으로 10007로 나눈나머지값이 아니라, 분해해서 곱할때마다 10007로 나눠서 그 나머지값에 또 분해 곱을 곱해야하는거더라...

글로 쓰니까 좀 말이 이상하긴한데.. ㅠ ㅠ표현을 잘못하겠다.

시험끝나면 본격적으로 달려볼까 한다.