소마 온라인 코딩테스트 1번 문제 복기

처음에 이렇게 거창하게 dfs 로 풀겠다고 설쳤다..

 

아니근데 n 이 2이상 1000이하. 최소 획수를 가진 1만을 가진다 가정하면 최대 500자리가 된다. 

 

이건 직접 숫자를 계산해서 비교하라는게 아닐 꺼라는 생각이 들었다. 잘못 접근하는 중이었다.. 

#include <iostream>
#include <vector>
#define MAX 10

using namespace std;

int arr[MAX]; // 0~9 까지 숫자의 획 수
int selected[501]; // 만들 수 있는 숫자 조합. n 이 최대 1000이고, 가장 적은 획수로 만들 수 있는 숫자 1의 획 수는 2이므로. 1000/2 = 500 이므로 최대 가능한 자리수는 500자리
long long max_num = 0; //최대 수 = 정답.

void dfs(int zari, int n) {
	if (n >= 0) {
		long long m = 0;
		for (int i = 0; i < zari; i++) {
			m = m + pow(10,i) * selected[i];
		}
		if (max_num < m)
			max_num = m;
	}

	if(n<0)
		return;

	for (int i = 0; i < 10; i++) {
		selected[zari] = i;
		dfs(zari + 1, n - arr[i]);
	}
	

}

int main() {
	arr[0] = 6;
	arr[1] = 2;
	arr[2] = 5;
	arr[3] = 5;
	arr[4] = 4;
	arr[5] = 5;
	arr[6] = 6;
	arr[7] = 3;
	arr[8] = 7;
	arr[9] = 6;

	int n;
	cin >> n;

	dfs(0, n);

	cout <<max_num;

	return 0;
}

 

어짜피 자리수 높은게 최곤데... 라는 생각이 머물다 허무한 규칙을 발견해냈다.

 

즉, 

표현할 숫자	0	1	2	3	4	5	6	7	8	9
획 수	6	2	5	5	4	5	6	3	7	6

획 수를 잘 보면, 어짜피 자리수에 제한이 없으니 짝수일때는 n/2 자리를 1로, 홀수일때는 7한개와 n/2-1 자리는 1로 채우는 것이 결국은 가장 큰 숫자가 될 것이다. 2이상의 모든 수는 2와 3을 가지고 덧셈식으로 표현할 수 있다.

 

아무튼 이런식으로 하면 된다.

#include <iostream>

using namespace std;

int main() {
	int n;
	cin >> n;

	int zari = 0; //자릿수

	if (n % 2 == 0) {
		zari = n / 2;
	}

	else {
		zari = n / 2 - 1;
		cout << "7";
	}

	for (int i = 0; i < zari; i++) {
		cout << "1";
	}


	return 0;
}

이렇게 O(N/2) 만에 해결가능..

 

허무하다 괜히 시간도 낭비했다. 처음부터 감을 잘 잡았으면 정말 20초컷이다ㅋㅋ

 

알고리즘 풀면서 항상 느끼는 거지만.. 머리가 안좋으면 몸이 고생함.