백준 1020: 디지털 카운터

OvO·2020년 8월 4일
0

BOJ

목록 보기
2/2

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

문제
지민이는 매 초마다 수가 증가하는 N자리의 디지털 카운터를 가지고 있다. 카운터에 나오는 수는 순환된다. 10^N-1에 이르면 다시 0부터 시작한다.
각 숫자는 다음과 같은 7개의 선분으로 이루어져 있다.

모든 인접한 두 개의 선분은 +로 이어져 있다. 예를 들어, 1은 두 개의 선분, 9는 다섯 개의 선분으로 이루어져 있다.
현재 카운터에 나와있는 숫자가 주어진다. 그럴 때, 현재 나와있는 숫자의 선분의 개수와 같은 숫자는 최소 몇 초가 지나야 나오는지 구하는 프로그램을 작성하시오.
1, 2, ..., 9, 그리고 0은 모두 2, 5, 5, 4, 5, 6, 3, 7, 5, 6개의 선분으로 이루어져 있고, 모든 수는 N자리를 채워야 하므로, N자리보다 작을 때는 앞에 0이 있을 수도 있다.

입력
첫째 줄에 현재 카운터에 나와있는 수가 주어진다. N은 그 수의 길이와 같다. (수가 0으로 시작할 수도 있음) 그리고, N은 15보다 작거나 같은 자연수이다.

출력
첫째 줄에 최소 몇 초가 지나야 현재 카운터에 나와 있는 수와 선분의 개수가 같아지는지 출력한다.

예제 입력 1
007

예제 출력 1
11

🤔생각

이전에 풀었던 1040문제와 비슷한 문제라고 느껴졌다. 그리고 차이점으로는 1040번에서는 각 숫자가 나왔는지 여부만 중요했다면 이 문제에서는 각 숫자가 나온 횟수도 중요했다. 각 횟수를 모두 기록하려면 15^10Byte가 필요한데 이는 너무 큰 공간을 차지한다. 그래서 숫자의 선분갯수가 같은 것들은 같은 공간으로 처리하였다. 숫자의 선분갯수는 2 ~ 7까지의 범위를 갖고 있으므로 15^7Byte만큼의 공간이 필요하다. 그리고 이를 활용하여 DP를 수행하면 중복되는 경우가 생겨 시간초과를 피할 수 있을 거라 생각했다.

👏코드

#include<iostream>
#include<algorithm>
#include<string>
#include<math.h>
#include<cstring>

using namespace std;

string strNum;
int digit[10] = { 6,2,5,5,4,5,6,3,7,5 };
char cache[16][16][16][16][16][16][2];
long long ans;

int cntEdge(long long num, int size) {
	int cnt = 0;

	for (int i = 0; i < size; i++) {
		cnt += digit[num % 10];
		num /= 10;
	}

	return cnt;
}

int time(long long currentNum, int cnt2, int cnt3, int cnt4, int cnt5, int cnt6, int cnt7, int objCnt, int pass, int len, int idx, long long num) {
	if (idx == len) {
		if (2 * cnt2 + 3 * cnt3 + 4 * cnt4 + 5 * cnt5 + 6 * cnt6 + 7 * cnt7 == objCnt) {
			if (pass == 0 && currentNum == num)
				return 0;
			ans = currentNum;
			return 1;
		}
		return 0;
	}
	
	char& ret = cache[cnt2][cnt3][cnt4][cnt5][cnt6][cnt7][pass];

	if (ret != -1)
		return ret;

	ret = 0;
	for (int i = pass == 1 ? 0 : (strNum[idx] - '0'); i < 10; i++) {
		int newPass = pass == 1 || i > strNum[idx] - '0';

		ret = time(10 * currentNum + i, cnt2 + (int)(digit[i] == 2), cnt3 + (int)(digit[i] == 3), cnt4 + (int)(digit[i] == 4), cnt5 + (int)(digit[i] == 5), cnt6 + (int)(digit[i] == 6), cnt7 + (int)(digit[i] == 7), objCnt, newPass, len, idx + 1, num);
		if (ret != 0)
			return ret;
		if (idx == 0 && i == 9) {
			i = -1;
			pass = 1;
		}
	}
	return ret;
}

int main(void) {
	int N, cnt;
	long long limit;
	memset(cache, -1, sizeof(cache));
	cin >> strNum;
	N = strNum.size();
	limit = pow(10, N);
	cnt = cntEdge(stoll(strNum), N);

	time(0, 0, 0, 0, 0, 0, 0, cnt, 0, N, 0, stoll(strNum));

	if (ans - stoll(strNum) == 0)
		cout << (ans - 1 - stoll(strNum) + limit) % limit + 1;
	else
		cout << (ans - stoll(strNum) + limit) % limit;
	return 0;
}

👏후기

이 문제를 풀고 다른 사람들이 제출한 코드를 봤었다. 나의 코드에서는 DP를 할 때 선분이 같은 것들의 갯수로 구분하였는데 다른 분들은 현재까지 몇자리를 채웠는지 그리고 현재까지 나온 선분갯수가 몇개인지로 구분하여 DP를 하셨다. 이 문제에서 중요한건 몇개의 숫자가 나오는지가 아닌 선분의 합이 중요했으므로 다른 사람의 풀이가 훨씬 깔끔하고 효율적이었다.

profile
이유재입니다.

0개의 댓글