백준 1025 제곱수 찾기 리뉴얼!! c++, Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/1025

1025번: 제곱수 찾기

문제

지민이는 천장을 보다가 직사각형 격자판을 생각했고, 각 칸에 숫자를 한 자리씩 적어 놓았다.

수업시간이 너무 지루해서 지민이는 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열을 생각해 보았다. 그리고 나서 그 수열의 수를 모두 이어 붙였다. 이렇게 만든 수 중에 가장 큰 제곱수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 지민이가 만든 수 중에 가장 큰 제곱수를 출력한다. 만약 제곱수가 없다면 -1을 출력한다.

알고리즘 분류

• 구현
• 브루트포스 알고리즘

풀이

백준 님도 이해가 안 간다는 레전드 불친절한 문제다.

현재 BOJ 골드 난이도, 프로그래머스 LEVEL3 정도의 문제를 30분 안에 푸는 연습을 하고 있는데,

질문 검색 찾아가며 문제 이해하는 데만 15분 걸린 것 같다. (문제 보고 풀기 싫어져서 딴짓도 조금..)

 

2 3

123

456

 

우선 어떤 문제인지 설명하자면, 입력이 위와 같을 때 64를 출력해야 한다.

64는 8의 제곱이기 때문에 일단 제곱수라는 조건은 만족하는데,

어떻게 64가 나왔을까?

주어진 2차원 배열에서

4 == (1,0)

6 == (1,2)

(1,2)의 값 6과 (1,0)의 값 4를 이어 붙였는데,

이는 행의 공차가 0, 열의 공차가 -2로

조건 '행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열'을 만족하게 된다.

 

이제 조금 감이 온다.

문제에서 말하는 수열의 수를 모두 이어붙인 값은 주어진 입력을 예로 들 때,

행의 공차는 -2~2

열의 공차는 -1~1

의 경우일 때 수열을 모두 구해서 제곱수인지 확인하고, 가장 큰 제곱수를 출력해야 하는 문제인 것이다!

 

행의 공차 =0 열의 공차 =1 인 경우엔 1이 가장 큰 제곱수가 된다.

(0,0) ==1

(0,1) ==2

(0,2) ==3

(0,0)+(0,1) ==12

(0,1)+(0,2) ==23

(0,0)+(0,1)+(0,2) ==123

(1,0) ==4

(1,1) ==5

(1,2) ==6

(1,0)+(1,1) ==45

(1,1)+(1,2) ==56

(1,0)+(1,1)+(1,2) ==456

 

이런 식으로 행과 열의 공차를 모두 구하고, 해당 공차들의 모든 등차수열을 검사하려면 

4개 이상의 반복문이 중첩되는데, 입력의 최대가 10이기 때문에 0ms의 시간 결과가 나온다.

 

※0도 제곱수이기 때문에 0만 주어졌을 때 출력은 -1이 아니라 0임에 주의하자

 

 

2022.04.21 코틀린 코드 추가

9개월 만에 코틀린으로 다시 풀었다.

틀려서 게시판에서 반례를 보고 다시 제출했는데,

이전에 내가 게시글로 올렸던 반례였다.

1 1

9

9달 전의 내 게시글이 나를 도운 것이다..!

그리고 포스팅을 하려 왔는데 아~ 이게 이 문제였구나..

위를 보면 알겠지만 원래 문제가 되게 불친절했다.

지금은 운영자님께서 바꿔주셨으니 좀 쉽게 풀 수 있을 것이다~ 

코드1(C++)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;
int n, m, answer = -1;//n ==r m//c
vector<string> input;


//제곱수면 제곱수를 반환
int toSquare(int num) {
	int squareRoot = sqrt(num);
	if(squareRoot*squareRoot==num)
		return num;
	else 
		return - 1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m; 

	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		input.push_back(str);
	}
	//input[r][c]가 등차수열의 시작점
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < m; c++) {
			//행의 공차와, 열의 공차를 구하는데, -인 경우도 구해야 한다.
			for (int dr = -n + 1; dr < n; dr++) {
				for (int dc = -m + 1; dc < m; dc++) {
					//행과 열의 공차가 모두 0이면 무한루프
					if (dr == 0 && dc == 0)
						continue;
					int a = r, b = c;
					string str="";
					//해당 행과 열의 공차에서 나오는 수열의 모든 값을 검사한다.
					while (a >= 0 && a < n && b >= 0 && b < m) {
						str += input[a][b];
						answer = max(answer,toSquare(stoi(str)));
						a += dr;
						b += dc;
					}
				}
			}
		}
	}
	//n과m이 1이면 반복문을 돌지 않기 때문에 따로 검사해 준다.
	if (n == 1 && m == 1) {
		cout <<toSquare(input[0][0]-'0');
	}
	else
	cout << answer;

}

코드2(Kotlin)

val br = System.`in`.bufferedReader()

fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
val set = mutableSetOf<Int>()
lateinit var graph: Array<String>
var answer = -1
val dir = arrayOf(
    arrayOf(0,1),
    arrayOf(1,0),
    arrayOf(1,1),
    arrayOf(1,-1)
)
fun pick(r: Int, c: Int, result: StringBuffer, d: Int, stepR: Int, stepC: Int,n: Int,m: Int){
//    println("$result")
    val result1 = result.toString().toInt()
    val result2 = result.toString().reversed().toInt()
    answer = if(set.contains(result1)) answer.coerceAtLeast(result1) else answer
    answer = if(set.contains(result2)) answer.coerceAtLeast(result2) else answer

    val nr = r+dir[d][0]*stepR
    val nc = c+dir[d][1]*stepC
    if(nr !in 0 until n || nc !in 0 until m) return

    pick(nr,nc,result.append(graph[nr][nc]), d, stepR, stepC, n, m)

}

fun main() =with(System.out.bufferedWriter()){
    //input
    val (n,m) = getIntList()
    graph = Array(n){br.readLine()}

    //preset
    for(i in 0 .. 40000){
        set.add(i*i)
    }
    //solve
    //모든 점에서 시작
    for(r in 0 until n){
        for(c in 0 until m){
            //우 하 하대각2
            for(i in 0 until 4){
                //step 1 ~
                for(stepR in 1 .. n) {
                    for(stepC in 1 .. m) {
                        pick(r, c, StringBuffer(graph[r][c].toString()), i, stepR, stepC, n, m)
                    }
                }
            }
        }
    }

    //output
    write("$answer")
    close()
}