[BOJ][백준]dp-18118번 7-세그먼트 디스플레이

 

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

18118번: 7-세그먼트 디스플레이

문제

7-세그먼트 디스플레이란 아래와 같이 7개의 선분으로 글자를 표시할 수 있는 장치를 말한다.

최근 시프트는 디지털 회로에 관한 강의를 듣고 있다. 시프트가 이번 주에 받은 과제의 내용은 아래와 같다.

7-세그먼트 디스플레이 n개를 사용한 회로를 구성한다. 양의 정수 m을 입력받아, n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 표시하시오.

다행히도 입출력은 강의자료에 전부 나와 있어서 그대로 따라 하면 됐기 때문에 별로 문제가 될 건 없었다. 더군다나, n자리 수로 만들 수 있는 가장 큰 m의 배수를 계산하는 건 너무 쉽다.

하지만 시프트는 놀라운 발견을 하게 되는데, 7-세그먼트 디스플레이 하나에는 0~9의 숫자뿐만 아니라 11도 표시할 수 있다는 사실이었다.

두 개의 7-세그먼트 디스플레이로 1을 표시하는 대신 한 개의 디스플레이로 11을 표시하면 한 자리를 아낄 수 있고, 이 방법으로 더 큰 m의 배수를 표현할 수 있을지도 모른다. 예를 들어 4자리 수 중 가장 큰 3의 배수는 9999이지만, 4개의 디스플레이로 만들 수 있는 가장 큰 3의 배수는  9   11   11   11이다.

이 방법을 활용해, 정수 n과 m에 대해 시프트가 n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 출력하라.

입력

첫 번째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 25)

각 테스트 케이스는 한 줄로 이루어져 있으며, 두 개의 수 n과 m이 주어진다. (1 ≤ n ≤ 9, 1 ≤ m ≤ 10^5)

출력

각 테스트 케이스마다 n개의 7-세그먼트 디스플레이에 표현할 수 있는 가장 큰 m의 배수를 한 줄에 하나씩 출력한다.

 

 

 

****************************************************************************************************************

 

대략 5시간 동안  12트만에 AC를 받은 문제입니다. 별거 아닌 문제 같았는데 결론은 별거 많은 문제였습니다.

7 세그 디스플레이에 11을 표기한다는 점이 포인트인 문제이고, 이것이 만악의 근원입니다.

처음 생각한 풀이는 백트래킹이었습니다. 나름대로 가지치기를 좀 했는데 시간 초과가 나서 다른 알고리즘을 사용했지만

다른 분의 풀이를 보니 비트 마스킹을 이용해서 백트래킹에 성공하신 분이 있었습니다. 시간적으로나 메모리량으로 보나

훨씬 더 퍼포먼스가 좋았습니다. 제가 구현한 백트래킹과 차이점이 있다면 비트 마스킹이었는데, 

N자릿수 중 11을 사용한 자릿수를 비트를 키는 것으로 구현을 하면 됩니다. 또한 11을 N-1개 사용해서 m으로 나누어

떨어지게 만든 값이 존재한다면 11을 N-2개 사용하여 만든 값이 반드시 더 작음이 보장됩니다. 당연하게도 자릿수가 더 

적게 되기 때문입니다. 코드를 적진 않지만최적화를 잘한 백트래킹도 풀이가 가능합니다.

본격적으로 dp풀이에 들어가기 전에, 저의 풀이는 N^2*M풀이이며, 정해는 NM풀이가 존재합니다.

재귀 dp(top-down)로 NM풀이는 불가능한 것 같습니다. 반복 dp(bottom-up)로는 NM풀이가 가능합니다.

다른 코드와 비교해서 메모리가 과다하게 많이 드는 코드이니, 이런 풀이가 있구나.. 정도만 알아두시면 좋습니다.

 

재귀 함수 f(n, r)을 N개의 디스플레이 중 n번째(0... N-1) 디스플레이를 결정할 차례이고, 나머지는 r인수로 정의합시다.

그리고 기저 사례(종료 조건)를 n이 N이고 r이 0이면 정상종료, r이 0이 아니면 실패(-INF)를 반환하면 됩니다.

점화식을 다음과 같이 세울 수 있습니다. 하지만 탑다운 방식의 한계가 여기서 나타납니다.

자릿수를 알지 못하는데 어떻게 값들을 더하냐는 겁니다.

//n번째 디스플레이에 11을 추가할때
ret=max( ret ,f(n+1,(100*r+11))+(??) )

//n번째 디스플레이에 i(0~9)를 추가할때
ret=max( ret, f(n+1,(10*r+i))+(??) )

 

 

답이 몇 자릿수인지 모르니 10의 제곱을 얼마만큼 곱해야 하는지 모릅니다. 그럼, 답이 몇 자릿수인지 알면 

10의 제곱을 얼마만큼 곱해야 하는지 알 수 있겠네요. dp함수를 한 개 더 만들어 cnt(n, r) 함수를 만들어서

11을 최대 몇 개까지 디스플레이에 포함시킬 수 있는지 구할 수 있습니다. 

int cnt(int n, int r)
{
	if (n == N)
	{
		if (r == 0) return 0;
		else return -100;
	}
	int&ret = cache2[n][r];
	if (ret != -1)return ret;

	ret = cnt(n + 1, (100 * r + 11) % M) + 1;
	for (int i = 0; i<10; i++)
		ret = max(ret, cnt(n + 1, (10 * r + i) % M));

	return ret;
}

cnt함수를 구현했으니 아까 절반만 완성됐던 점화식을 완성시켜보면,

 

//n번째 디스플레이에 11을 추가할때
ret=max( ret ,f(n+1,(100*r+11))+ 11 * pow(10, N - n - 2 + add) )

//n번째 디스플레이에 i(0~9)를 추가할때
ret=max( ret, f(n+1,(10*r+i))+ i * pow(10, N - n - 1 + add) )

여기서 add는 디스플레이에 표시해야 할 남은 11의 개수입니다. 이제 전체 코드를 봅시다.

라이브러리의 pow함수의 double형 오류를 방지하기 위해 myPow함수를 따로 정의하여 사용하였습니다.

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <limits.h>
using namespace std;
typedef long long ll;
int N, M;
ll cache[10][100000 + 2][10];
int cache2[10][100000 + 2];

ll myPow(int n, int k)
{
	if (k == 0)return 1;
	return myPow(n, k - 1)*n;
}

int cnt(int n, int r)
{
	if (n == N)
	{
		if (r == 0) return 0;
		else return -100;
	}
	int&ret = cache2[n][r];
	if (ret != -1)return ret;

	ret = cnt(n + 1, (100 * r + 11) % M) + 1;
	for (int i = 0; i<10; i++)
	 ret = max(ret, cnt(n + 1, (10 * r + i) % M));

	return ret;
}

ll f(int n, int r, int add)
{
	if (n == N)
	{
		if (r == 0 && add==0) return 0;
		else return LLONG_MIN + 100;
	}
	ll&ret = cache[n][r][add];
	if (ret != -1)return ret;
	ret = LLONG_MIN + 100;
	//use 11
	if (add) ret = f(n + 1, (100 * r + 11) % M, add - 1) + 11 * myPow(10, N - n - 2 + add);
	//use 0~9
    	for (int i = 9; i >=0; i--)
			ret = max(ret, f(n + 1, (10 * r + i) % M, add) + i*myPow(10, N - n - 1 + add));
	

	return ret;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while (t--)
	{
		memset(cache, -1, sizeof(cache));
		memset(cache2, -1, sizeof(cache2));
		cin >> N >> M;
		cout << f(0, 0, cnt(0, 0));
		cout << "\n";
	}
}

코드가 완성되었습니다! 그리고 이 코드를 제출하면 38% 즈음에서 얄밉게도 시간 초과가 납니다.

매 테스트 케이스마다 두 개의 cache를 초기화해주고, dp함수를 2개나 돌리니 어쩌면 당연했을 겁니다.

여기에 약간의 커팅을 더하면 시간제한을 간신히 통과합니다. f함수는 주어진 add개의 11을 다 쓰지 않으면 실패로 간주합니다. 따라서 N-n보다 add가 같거나 크다면 남은 디스플레이보다 사용해야 할 add가 더 많다는 의미이므로

0~9를 반복문으로 볼 필요 없이 얼른 11을 띄우고 종료하면 됩니다. 다음과 같은 코드를 중간에 추가해 줍시다.

if(N-n<=add) return ret= f(n + 1, (100 * r + 11) % M, add - 1) + 11 * myPow(10, N - n - 2 + add);

길고 긴 여정 끝에 드디어 AC를 받을 수 있습니다.

이렇게 꽉 막힌 사고로 재귀 방식의 dp를 선호하다 보면 결국 머리와 몸이 고생하게 됩니다.

 

탑다운 dp 안다고 바텀업 dp 무시하지 말고

세그먼트 트리 안다고 팬윅트리 무시하지 말고

디익스트라 안다고 벨만 포드 무시하지 말자.

 

가 오늘의 교훈입니다. 저에게 다 해당되는 내용입니다ㅠ...