오늘의 한 마디
제한이 매우 작으면, 4중 for문도 쓸 수 있구나~ 플로이드-워셜처럼
문제
N행 M열의 표 A가 있고, 표의 각 칸에는 숫자가 하나씩 적혀있다.
연두는 서로 다른 1개 이상의 칸을 선택하려고 하는데, 행의 번호가 선택한 순서대로 등차수열을 이루고 있어야 하고, 열의 번호도 선택한 순서대로 등차수열을 이루고 있어야 한다. 이렇게 선택한 칸에 적힌 수를 순서대로 이어붙이면 정수를 하나 만들 수 있다.
연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자. 완전 제곱수란 어떤 정수를 제곱한 수이다.
입력
첫째 줄에 N, M이 주어진다. 둘째 줄부터 N개의 줄에는 표에 적힌 숫자가 1번 행부터 N번 행까지 순서대로 한 줄에 한 행씩 주어진다. 한 행에 적힌 숫자는 1번 열부터 M번 열까지 순서대로 주어지고, 공백없이 모두 붙여져 있다.
출력
첫째 줄에 연두가 만들 수 있는 가장 큰 완전 제곱수를 출력한다. 만약, 완전 제곱수를 만들 수 없는 경우에는 -1을 출력한다.
제한
1 ≤ N, M ≤ 9
표에 적힌 숫자는 0보다 크거나 같고, 9보다 작거나 같다.
예제 입력 1
2 3
123
456예제 출력 1
64만들 수 있는 세자리 수는 123, 321, 456, 654이다. 이 중 완전 제곱수는 없기 때문에 정답은 64가 된다.
예제 입력 2
5 5
00000
00000
00200
00000
00000예제 출력 2
00은 완전 제곱수이고, 입력으로 주어진 표에서 만들 수 있는 가장 큰 완전 제곱수이다.
예제 입력 3
6 7
3791178
1283252
4103617
8233494
8725572
2937261예제 출력 3
320356모든 i번 행의 i번 열에 적힌 수를 이어붙이면 320356을 만들 수 있고, 이 수는 5662 = 320356 이다.
예제 입력 4
5 9
135791357
357913579
579135791
791357913
913579135예제 출력 4
9홀수 숫자 두 개로 끝나는 완전 제곱수는 없다. 따라서, 만들 수 있는 가장 큰 완전 제곱수는 9이다.
예제 입력 5
9 9
553333733
775337775
777537775
777357333
755553557
355533335
373773573
337373777
775557777예제 출력 5
-13, 5, 7만을 이용해 완전 제곱수를 만들 수 없다.
예제 입력 6
9 9
257240281
197510846
014345401
035562575
974935632
865865933
684684987
768934659
287493867예제 출력 6
95481다음과 같이 굵게 표시된 숫자를 이어붙이면 95481을 만들 수 있다.
257240281
197510846
014345401
035562575
974935632
865865933
684684987
768934659
287493867
발상
행의 번호가 등차수열을 이루고, 열의 번호가 등차수열을 이룬다..?
굉장히 생소한 조건이다.
12345
67890
90123여기서 만들 수 있는 수를 한번 생각해보자.
12345, 54321, 169 이런 것 뿐만이 아니라
[2][4] -> [1][2] -> [0][0]으로 이어지는 381도 만들 수 있다!
도저히 감이 안 잡힌다.
해설
4중 for문과 while문을 이용한다. 가장 바깥쪽 for문 2개는 행의 시작 위치와 열의 시작 위치를 정한다. 그 다음 for문 2개는 행 방향 등차와 열 방향 등차를 정한다.
4중 for문..?
알고리즘 분류가 브루트포스인 이유가 있었다.
모든 경우의 수를 다루기 위해서는 4가지 정보가 필요하다.
(y, x) 시작점 값, y의 공차, x의 공차
진짜 4중 for문을 써서 이 모든 경우의 수를 다 조합해본다.
N과 M은 1~9의 제한이 걸려있으므로, 10*10*10*10 = 10000이고,
통상적으로 1초에 1억번의 연산을 한다고 생각하면 매우 널널하다.
Try #1
import sys
import math
N, M = map(int, sys.stdin.readline().rstrip().split())
graph = []
for _ in range(N):
graph.append(list(map(int, list(sys.stdin.readline().rstrip()))))
def f(y, x, y_diff, x_diff):
if y_diff == 0 and x_diff == 0:
return graph[y][x]
answer = graph[y][x]
while 0 <= y+y_diff < N and 0 <= x+x_diff < M:
y, x = y+y_diff, x+x_diff
answer *= 10
answer += graph[y][x]
return answer
# y, x, y공차, x공차
answer = -1
for y in range(N):
for x in range(M):
for y_diff in range(-N, N):
for x_diff in range(-M, M):
n = f(y, x, y_diff, x_diff)
n_sqrt = math.sqrt(n)
if n_sqrt - int(n_sqrt) == 0:
answer = max(answer, n)
print(answer)틀렸습니다를 받았다.
왜일지 생각해봤는데, f를 써서 만들어지는 수를 별도의 함수로 분리하여 가독성을 높이려 했던게 잘못이었다.
이전 풀이의 반례
3 3
777
767
771정상 출력: 16, 현재 출력: 1오작동 이유 : 1, 16, 167을 전부 검사해야 하는데, (2,2) 점에서 공차(-1,-1)로 만들어진 수를 f에 넣으면 최대 길이인 167을 반환하기 때문에 167만 검사했었음.
풀이
import sys
import math
N, M = map(int, sys.stdin.readline().rstrip().split())
graph = []
for _ in range(N):
graph.append(list(map(int, list(sys.stdin.readline().rstrip()))))
def is_perfect_square(n):
n_sqrt = math.sqrt(n)
return n_sqrt - int(n_sqrt) == 0
# y, x, y공차, x공차, 수의 길이
answer = -1
for y in range(N):
for x in range(M):
for y_diff in range(-N+1, N):
for x_diff in range(-M+1, M):
i, j = y, x
n = graph[i][j]
if y_diff == 0 and x_diff == 0:
if is_perfect_square(n):
answer = max(answer, n)
continue
while 0 <= i+y_diff < N and 0 <= j+x_diff < M:
i, j = i+y_diff, j+x_diff
n *= 10
n += graph[i][j]
if is_perfect_square(n):
answer = max(answer, n)
if is_perfect_square(n):
answer = max(answer, n)
print(answer)