글 읽기 - 어디서 틀린건지 모르겠네요..

simm4256 7년 전 0

70%까지 갔다가 틀렸다고 나오네요.

제가 푼 알고리즘은 다음과 같습니다.

1. n,m이 주어지면 가능한 공차는 (1-n ~ n , 1-m ~ m)이다.

예를 들어 n=2, m=3이면 행에서 등차수열을 만들 때 가능한 공차는 -1,0,1이고 열에선 -2~2이다.

각 공차의 조합에 대해 모든 경우를 탐색한다.

2. 탐색할 공차의 조합을 정했다면 어느 위치에서부터 탐색을 시작할지 정한다.

이 또한 (1~n, 1~m)이 가능한데, n=2, m=3이면 가능한 시작 위치는 (1,1), (1,2), (1,3), (2,1), (2,2), (2,3)이다.

이 모든 경우를 탐색한다.

3. 탐색할 공차와 시작위치를 정했다면 시작위치의 숫자부터 주어진 공차로 이동하여 한 숫자씩 붙여가며 제곱수인지 확인한다.

ex)

n=2, m=3일 때 공차가 -1,1이고 시작위치가 (2,1)이고

주어진 배열이

123

456

이라면

4, 42

에 대해 제곱수인지 확인하고 현재까지 구한 가장 큰 제곱수를 저장한다.

4. 1~3을 반복하여 가장 큰 제곱수를 찾는다.

알고리즘상에는 전혀 문제가 없어보이는데..

코드상에 문제가 있는걸까요?

도저히 모르겠네요..

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#pragma warning(disable:4996)
using namespace std;

int n, m, arr[9][9];

int main() {
	int i,j,k,time,x,y,a,b,max=-1,tempResult;
	char temp[20];
	double check;
	cin >> n >> m;
	for(i=0;i<n;i++)
		for(j=0;j<m;scanf("%1d",&arr[i][j++]));
	for (i = 1 - n; i < n; i++) {
		for (j = 1 - m; j < m; j++) { //i,j는 공차
			if (i == 0 && j == 0) continue;  //공차가 둘 다 0일 경우, 즉 1자리수만 검사할 경우는 나중에 함
			for (x = 0; x < n; x++) {
				for (y = 0; y < m; y++) { //x,y는 시작 위치. ex) x=0,y=0이고 i=1,j=1이면 arr[0][0]부터 시작해 arr[1][1], arr[2][2]순으로 탐색해나간다.
					a = x; b = y; time = 0;  //a,b는 처음엔 시작위치 좌표였다가 공차에 의해 변하는 유동좌표, time은 몇 자리 숫자인지를 결정
					do {
						temp[time++] = arr[a][b] + 48;
						if (time > 1) {  //한자리 숫자에 대해선 수행하지 않음 (나중에 일괄수행)
							temp[time] = NULL;
							tempResult = atoi(temp);  //tempResult는 현재까지 탐색한 수
							check = sqrt((double)tempResult);
							if ((max < tempResult) && (check - (double)((int)check) == 0))  //tempResult의 제곱근이 정수일 경우, 즉 tempResult가 제곱수일 경우 현재 확인된 제곱수중 가장 큰 수인 max보다 크면 max=tempResult
								max = tempResult;
						}
						a += i; b += j;
					} while (a >= 0 && a < n && b >= 0 && b < m); 
				}
			}
		}
	}
	if (max < 9) { //현재 탐색한 제곱수의 가장 큰 값이 9보다 작은 한 자리수이면, 배열의 모든 수 확인
		for (i = 0; i < n; i++) {
			for (j = 0; j < m; j++) {
				if ((arr[i][j] == 1 || arr[i][j] == 4 || arr[i][j] == 9) && max < arr[i][j]) {
					max = arr[i][j];
					if (max == 9) break;
				}
			}
			if (max == 9) break;  //제곱수가 9이면 한자리 수 중 가장 큰 값이므로 더이상 탐색하지 않음
		}
	}
	cout << max;
}

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