글 읽기 - 소스상에서 반례를 찾고있습니다

skskemfla 7년 전 0

안되는 반례가 뭐가 있을까요...

분명히 왠만한 값 넣어서는 다 잘 되고 코드 상 문제도 없어보이는데 잘 안되네요 ㅠㅠ

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

int main()
{
	int n;
	int realnum;
	scanf("%d", &n);
	if (n < 1 || n > 1000000) return 0;

	for (int m = 1; m < 10000001; m++) {
		int j = 0;
		int i = m;

		if (i < 10) {
			j = i;
		}
		else if(i < 100) {
			for (int k = 0; k < 2; k++) {
				int u  = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}
		else if (i < 1000) {
			for (int k = 0; k < 3; k++) {
				int u = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}
		else if (i < 10000) {
			for (int k = 0; k < 4; k++) {
				int u = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}
		else if (i < 100000) {
			for (int k = 0; k < 5; k++) {
				int u = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}
		else if (i < 1000000) {
			for (int k = 0; k < 6; k++) {
				int u = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}
		else if (i < 10000000) {
			for (int k = 0; k < 7; k++) {
				int u = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}
		else if (i < 100000000) {
			for (int k = 0; k < 8; k++) {
				int u = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}
		else {
			for (int k = 0; k < 9; k++) {
				int u = i % 10;
				i = i / 10;
				j = j * 10 + u;
			}
		}

		if (m - j == n) {
			realnum=m;
			break;
		}
		else realnum = -1;
	}

	printf("%d", realnum);

	return 0;
}

chogahui05 6년 전 0

간단하게 999990을 넣어봅시다. 답은 11000001입니다.

힌트만 하나 드릴게요. 발암 문제까지는 아니고, 사실 구현 문제에 가까운데요.

(1) 식을 잘 정리한다.

(2) 그리디하게 푼다.

x를 a(n)10^n + ... + a(0)10^0 꼴로 나타낼 수 있다고 치면

a(n) >= a(0)을 만족해야 하고요. 이것을 주의하셔야 합니다.

당연하게도, 그냥 무식하게 탐색하면

대충 10^12, 10^13 정도까지는 탐색해야 하니.. 시간 초과가 나는 건 당연한 소리겠지요.

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

문제

문제

출처

ICPC

소스상에서 반례를 찾고있습니다

skskemfla 7년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말