[baekjoon 20548] 칠리소스 (수학, 브루트포스) (C++)

www.acmicpc.net/problem/20548

20548번: 칠리소스

칠리소스는 7의 제곱수로 이루어져 있으며, 각 제곱수를 2개까지 이용이 가능하다.

예를 들어 7의 0 제곱수만큼의 캡사이신이 함유된 베이스 캡사이신 한 번과 7의 1 제곱수만큼의 캡사이신이 함유된 베이스 캡사이신 두 번의 조합으로 15만큼의 캡사이신이 함유된 72 칠리소스를 만들 수 있다. 그리고 이 소스의 매운맛 단계는 7이다. 1단계 매운맛의 경우 1만큼의 캡사이신이 함유된다.

 

정리하면

매운맛 단계	캡사이신 구성	함유량
1	7^0 * 1	1
2	7^0 * 2	2
3	7^0 * 0 + 7^1 * 1	7
4	7^0 * 1 + 7^1 * 1	8
5	7^0 * 2 + 7^1 * 1	9
6	7^0 * 0 + 7^1 * 2	14

이런 식으로 구성이 된다. 7단계는 예시에 써져있는 것처럼 15가 될 것이다.

즉, 7의 제곱수들을 각각 0~2번씩 사용해서 만들 수 있는 수들을 오름차순으로 정렬한 순서가 매운맛 단계이다.

 

또한, 수를 분석해보면 각 자릿수는 7의 제곱수로 구성되어 있고 0~2번씩 사용이 되었다.

매 자릿 수당 0~2를 사용하는 것이 3진수가 연상이 된다

 

따라서, 입력받은 함유량을 통해 단계를 출력하면 되므로

함유량을 7로 나눈 나머지를 3진수를 10진수로 바꾸듯이 계산하면 된다.

ex) 14는 7^1*2 + 7^0*0이고 20(3)이다. 10진수로 바꾸면 2 * 3^1 + 0 * 3^0 = 6이다.

 

+총 727272단계이므로 int형을 넘어간다.

 

#include <iostream>
#include <cmath>
using namespace std;

long long n, result, temp;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	// 수의 구성 : 7의 제곱수로 0~2(3진수형식)만큼
	// ex : 10의 제곱수로 10진수형식은 10으로 나누면 각 자릿수가 나오고 10진수형식이므로 10을 곱해주면 복원이 가능
	// 즉 이 수는 7의 제곱수로 3진수 형식이므로 7으로 나눈 나머지를 3으로 곱해주면 복원이 가능하다.

	int digit = 1;
	while (n) {
		result += (n % 7) * digit;
		n /= 7;
		digit *= 3; // 3진수형식이므로 한 칸당 3씩 늘어난다(0,1,2)
	}

	cout << result;
}