글 읽기 - 디지털 카운터 문제, 반례가 뭐가 있을까요?ㅜㅜ(c언어)

won123 4년 전 0

디지털 카운터 문제, 반례가 뭐가 있을까요?ㅜㅜ(c언어)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

long long int dp[16][151];	// i자리 합이 j가 되는 가장 작은 수
int cnt[10] = { 6,2,5,5,4,5,6,3,7,5 };
long long int pow10[16] = { 1,10,100,1000,10000,100000,1000000, 10000000, 100000000, 1000000000, 10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000 };
long long int mx = 0xfffffffffffffff;


long long int make_integer(char *s, int len) {
	long long int result = 0, tmp;
	int k = len;
	for (int i = 0; i < len;i++) {
		tmp = (s[i] - '0');
		for (int j = 1; j < k; j++) {
			tmp *= 10;
		}
		result += tmp;
		k--;
	}
	return result;
}

long long int mini(long long int a, long long int b) {
	return (a > b) ? b : a;
}
int main(void) {
	
	char str[17];
	int len, sum = 0, index, tmp = 0;
	char ans[17], new_ans[17], init_ans[17];

	for (int i = 0; i < 16; i++) {
		for (int j = 0; j < 150; j++) {
			dp[i][j] = mx;
		}
	}

	for (int j = 0; j < 10; j++) {
		dp[1][cnt[j]] = mini(dp[1][cnt[j]], j);
	}

	for (int i = 2; i <= 15; i++) {
		for (int msb = 0; msb <= 9; msb++) {
			for (int j = 0; j < 150; j++) {
				if (dp[i-1][j] == mx) continue;
				dp[i][j + cnt[msb]] = mini(dp[i][j + cnt[msb]], dp[i-1][j] + pow10[i - 1] * msb);
			}
		}
	}

	scanf("%s", str);
	len = strlen(str);

	ans[0] = '1';
	for (int i = 1; i <= len; i++) {
		ans[i] = '0';
	}
	ans[len + 1] = '\0';

	strcpy(init_ans, ans);
	index = len - 1;

	for (int i = 0; i < len; i++) {
		sum += cnt[(str[i] - '0')];
	}
	// 일의 자리에서 sum과 같은 수가 나올 때
	for (int i = 0; i <= 9; i++) {

		if (str[index] != '0' + i && cnt[i] - cnt[(str[index] - '0')] == 0) {
			if (!strcmp(ans, init_ans)) // 만약 ans에 변화가 없었을 때
			{
				strcpy(new_ans, str);
				new_ans[index] = i + '0';
				strcpy(ans, new_ans);
			}
			else {
				if (i + '0' > str[index]) {
					if ((ans[index] < str[index]) || (i + '0' < ans[index])) {
						strcpy(new_ans, str);
						new_ans[index] = i + '0';
						strcpy(ans, new_ans);
					}
				}
				else {
					if ((ans[index] < str[index]) && (i + '0' < ans[index])) {
						strcpy(new_ans, str);
						new_ans[index] = i + '0';
						strcpy(ans, new_ans);
					}
				}
			}
		}
	}

	// 십의 자리 이상에서 나올 때
	for (int i = 2; i <= len; i++) {
		index--;
		tmp = 0;
		for (int i = index; i < len; i++) {
			tmp += cnt[(str[i]-'0')];
		}

		for (int j = 0; j <= 9; j++) {
			if (j + '0' != str[index] && dp[i - 1][tmp - cnt[j]] != mx) {	// ans 갱신
					
					strcpy(new_ans, str);
					new_ans[index] = j + '0';
					int q = i - 2;
					int r = dp[i - 1][tmp - cnt[j]];
					for (int p = index + 1; p < len; p++) {
						new_ans[p] = (r / pow10[q] + '0');
						r %= pow10[q];
						q--;
					}

					if (!strcmp(ans, init_ans)) // 만약 ans에 변화가 없었을 때
					{
						strcpy(ans, new_ans);
					}

					else {		// ans에 변화가 있었을 때
						if (strcmp(ans, str) == -1) {	// ans이 str보다 왼쪽에 있을 때
							if (strcmp(new_ans, str) == 1)	// 만약 new_ans이 str보다 오른쪽에 있으면
							{
								strcpy(ans, new_ans);
							}
							else {
								if (strcmp(new_ans, ans) == -1) strcpy(ans, new_ans);
							}
						}

						else {	// ans이 str보다 오른쪽에 있을 때
							if (strcmp(new_ans, str) == 1 && strcmp(new_ans, ans) == -1) strcpy(ans, new_ans);
						}
					}
				
			}
		}
	}
	if (!strcmp(ans, init_ans)) printf("%lld\n", make_integer(init_ans,len) * 10);
	else{
		long long int result_ans = make_integer(ans, len);
		long long int result_init_ans = make_integer(init_ans, len) * 10;
		long long int result_str = make_integer(str, len);

		if (result_ans > result_str) printf("%lld\n", (result_ans - result_str));
		else {
			printf("%lld\n", result_init_ans - result_str + result_ans);
		}
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

디지털 카운터 문제, 반례가 뭐가 있을까요?ㅜㅜ(c언어)

won123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말