글 읽기 - 반례가 무엇인지 궁금합니다

y2h000123 4년 전 0

상위 문제를 먼저 풀다보니 수를 배열로 받고 있습니다만...

반례를 찾지를 못하겠습니다

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
int n;
struct number {
	int num[101] = { 0 };
	int value;
	int num_leg = 0;
}way[105][105];

number find(int x, int y) {
	number a;
	number b;
	if (x == n && y == n) {
		a.num[0] = 1;
		a.num_leg = 1;
		return a;
	}
	else if (x > n || y > n || way[x][y].value == 0) {
		a.num[0] = 0;
		a.num_leg = 1;
		return a;
	}
	else if (way[x][y].num_leg > 0) return way[x][y];
	way[x][y].num[0] = 0;
	way[x][y].num_leg = 1;
	a = find(x + way[x][y].value, y);
	b = find(x, y + way[x][y].value);
	for (int i = 0; i < a.num_leg || i < b.num_leg; i++) {
		if (way[x][y].num[i] > 9) {
			int temp = way[x][y].num[i];
			way[x][y].num[i + 1] += temp / 10;
			way[x][y].num[i] = temp % 10;
			way[x][y].num_leg++;
		}
		way[x][y].num[i] += a.num[i];
		way[x][y].num[i] += b.num[i];
		if (way[x][y].num[i] > 0 && i == way[x][y].num_leg) way[x][y].num_leg++;
	}
	return way[x][y];
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &way[i][j].value);
			way[i][j].num[0] = -1;
		}
	}
	number get;
	get = find(1, 1);
	for (int i = 0; i < get.num_leg ; i++) {
		if (get.num[i] > 9) {
			int temp = get.num[i];
			get.num[i + 1] += temp / 10;
			get.num[i] = temp % 10;
			get.num_leg++;
		}
		if (get.num[i] > 0 && i == get.num_leg) get.num_leg++;
	}
	for (int i = get.num_leg - 1; i >= 0; i--) {
		printf("%d", get.num[i]);
	}
	/*
	printf("\n");
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			get = way[i][j];
			for (int i = 0; i < get.num_leg; i++) {
				if (get.num[i] > 9) {
					int temp = get.num[i];
					get.num[i + 1] += temp / 10;
					get.num[i] = temp % 10;
					get.num_leg++;
				}
				if (get.num[i] > 0 && i == get.num_leg) get.num_leg++;
			}
			//printf(" %d",get.num_leg);
			for (int i = get.num_leg - 1; i < 5; i++) {
				printf(" ");
			}
			for (int i = get.num_leg - 1; i >= 0; i--) {
				printf("%d", get.num[i]);
			}
		}
		printf("|\n");
	}
	*/
}

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

문제

문제

출처

ICPC

반례가 무엇인지 궁금합니다

y2h000123 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말