https://www.acmicpc.net/problem/1025
-
문제
N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.
연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.
연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다. -
입력
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다. -
출력
첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.
이거 쉽다구 다른문제도 풀던데 난 어려웠당..ㅎ..
일단 아이디어 생각해내는거부터 막막했고 4중포문으로 x, y, x공차, y공차 하나하나 다 돌려갈 때 온갖 경우의 수가 나온다는 것을 이해하는 것도 시간이 걸린 것 같다
그리고 공차가 0, 0 일 때 무한루프를 돌게 되는 것을 생각하지못해서 무한루프 때문에 해결하는 데에 또 애를 먹었다,,
import math
N, M = map(int, input().split())
arr = []
for i in range(N):
arr.append(list(map(int, input())))
ans = -1
for i in range(N):
for j in range(M):
for n in range(-N, N):
for m in range(-M, M):
if m == 0 and n == 0: # 공차가 0이면 무한반복이어성
continue
x = i
y = j
cnt = 0 # 공차에 곱해줄 수
val = '' # 문자열
while 0<=x<N and 0<=y<M:
val += str(arr[x][y]) # 현재값을 문자열에 합쳐줌
cnt += 1
value = int(val)
value_sqrt = math.sqrt(value)
value_decimal = value_sqrt - int(value_sqrt)
if value_decimal == 0 and ans < value: # 제곱수이고 최대면
ans = value
x = i + cnt*n
y = j + cnt*m
print(ans)
🐢👩💻⛄🤍💜